The wisdom of social multimedia using flickr for prediction and forecast.

A Unified Framework for Link Recommendation Using Random Walks.
Abstract—The phenomenal success of social networking sites, such as Facebook, Twitter and LinkedIn, has revolutionized the way people communicate, and this paradigm have attracted the attention of researchers that wish to study the social and technological problems that arise. One such problem is that of link recommendation which is a critical task that not only helps improve the user experience but also is essential to network growth itself. In an effective link recommendation algorithm it is essential to identify the factors that influence link creation. This paper enumerates several of these well studied factors and then proposes an approach which satisfies these factors. This approach estimates link relevance by estimating the link relevance by using using random walk algorithm on an augmented social graph with both attribute and structure information. The global and local influence of the attributes is leveraged in the framework as well. Other than link recommendation, our framework can also rank the attributes in the social network. Experiments on DBLP and IMDB data sets demonstrate that our method outperforms state of the art methods for link recommendation. I.
Keyword Search in Text Cube Finding Top%2Dk Aggregated Cell Documents.



Mining topic%2Dlevel influence in heterogeneous networks.

SHRINK a structural clustering algorithm for detecting hierarchical communities in networks.

Visual cube and on%2Dline analytical processing of images.

Mining Diversity on Networks.

Incremental Clustering for Trajectories.

Mining Moving Object%2C Trajectory and Traffic Data.

Aggregation of Multiple Judgments for Evaluating Ordered Lists.
Abstract. Many tasks (e.g., search and summarization) result in an ordered list of items. In order to evaluate such an ordered list of items, we need to compare it with an ideal ordered list created by a human expert for the same set of items. To reduce any bias, multiple human experts are often used to create multiple ideal ordered lists. An interesting challenge in such an evaluation method is thus how to aggregate these different ideal lists to compute a single score for an ordered list to be evaluated. In this paper, we propose three new methods for aggregating multiple order judgments to evaluate ordered lists: weighted correlation aggregation, rank-based aggregation, and frequent sequential pattern-based aggregation. Experiment results on ordering sentences for text summarization show that all the three new methods outperform the state of the art average correlation methods in terms of discriminativeness and robustness against noise. Among the three proposed methods, the frequent sequential pattern-based method performs the best due to the flexible modeling of agreements and disagreements among human experts at various levels of granularity. Key words: Evaluation, Sentenceordering,Judgment aggregation,Frequent sequential pattern mining
Structure Is Informative On Mining Structured Information Networks.


Graph Regularized Transductive Classification on Heterogeneous Information Networks.


NDPMine Efficiently Mining Discriminative Numerical Features for Pattern%2DBased Classification.

Fast computation of SimRank for static and dynamic information networks.

Region%2Dbased online promotion analysis.

A worldwide tourism recommendation system based on geotaggedweb photos.

Top%2DK aggregation queries over large networks.

TopCells Keyword%2Dbased search of top%2Dk aggregated documents in text cube.

Progressive clustering of networks using Structure%2DConnected Order of Traversal.

Diagnostic powertracing for sensor node failure analysis.

Mining periodic behaviors for moving objects.


Mining advisor%2Dadvisee relationships from research publication networks.

On community outliers and their efficient detection in information networks.


Hierarchical Web%2DPage Clustering via In%2DPage and Cross%2DPage Link Structures.

Classification and Novel Class Detection in Data Streams with Active Mining.

MoveMine mining moving object databases.

Mining knowledge from databases an information network analysis approach.

Privacy%2Daware regression modeling of participatory sensing data.

RankCompete simultaneous ranking and clustering of web photos.

Keyword extraction for social snippets.

Entity relation discovery from web tables and links.
The World-Wide Web consists not only of a huge number of unstructured texts, but also a vast amount of valuable structured data. Web tables [2] are a typical type of structured information that are pervasive on the web, and Web-scale methods that automatically extract web tables have been studied extensively [1]. Many powerful systems (e.g., OCTOPUS [4], Mesa [3]) use extracted web tables as a fundamental component. In the database vernacular, a table is defined as a set of tuples which have the same attributes. Similarly, a web table is defined as a set of rows (corresponding to database tuples) which have the same column headers (corresponding to database attributes). Therefore, to extract a web table is to extract a relation on the web. In databases, tables often contain foreign keys which refer to other tables. Therefore, it follows that hyperlinks inside a web table sometimes function as foreign keys to other relations whose tuples are contained in the hyperlink’s target pages. In this paper, we explore this idea by asking: can we discover new attributes for web tables by exploring hyperlinks inside web tables? This poster proposes a solution that takes a web table as input. Frequent patterns are generated as new candidate relations by following hyperlinks in the web table. The confidence of candidates are evaluated, and trustworthy candidates are selected to become new attributes for the table. Finally, we show the usefulness of our method by performing experiments on a variety of web domains.
LINKREC a unified framework for link recommendation with user attributes and graph structure.
With the phenomenal success of networking sites (e.g., Facebook, Twitter and LinkedIn), social networks have drawn substantial attention. On online social networking sites, link recommendation is a critical task that not only helps improve user experience but also plays an essential role in network growth. In this paper we propose several link recommendation criteria, based on both user attributes and graph structure. To discover the candidates that satisfy these criteria, link relevance is estimated using a random walk algorithm on an augmented social graph with both attribute and structure information. The global and local influence of the attributes is leveraged in the framework as well. Besides link recommendation, our framework can also rank attributes in a social network. Experiments on DBLP and IMDB data sets demonstrate that our method outperforms state-of-the-art methods based on network structure and node attribute information for link recommendation.
Social group suggestion from user image collections.

iRIN image retrieval in image%2Drich information networks.

Topic initiator detection on the world wide web.

CETR content extraction via tag ratios.
We present Content Extraction via Tag Ratios (CETR) – a method to extract content text from diverse webpages by using the HTML document’s tag ratios. We describe how to compute tag ratios on a line-by-line basis and then cluster the resulting histogram into content and non-content areas. Initially, we find that the tag ratio histogram is not easily clustered because of its one-dimensionality; therefore we extend the original approach in order to model the data in two dimensions. Next, we present a tailored clustering technique which operates on the two-dimensional model, and then evaluate our approach against a large set of alternative methods using standard accuracy, precision and recall metrics on a large and varied Web corpus. Finally, we show that, in most cases, CETR achieves better content extraction performance than existing methods, especially across varying web domains, languages and styles.
Mining Concept%2DDrifting Data Streams.
Recently, mining data streams with concept drifts for actionable insights has become an important and challenging task for a wide range of applications including credit card fraud protection, target marketing, network intrusion detection, etc. Conventional knowledge discovery tools are facing two challenges, the overwhelming volume of the streaming data, and the concept drifts. In this paper, we propose a general framework for mining concept-drifting data streams using weighted ensemble classifiers. We train an ensemble of classification models, such as C4.5, RIPPER, naive Bayesian, etc., from sequential chunks of the data stream. The classifiers in the ensemble are judiciously weighted based on their expected classification accuracy on the test data under the time-evolving environment. Thus, the ensemble approach improves both the efficiency in learning the model and the accuracy in performing classification. Our empirical study shows that the proposed methods have substantial advantage over single-classifier approaches in prediction accuracy, and the ensemble framework is effective for a variety of classification models.
Re%2Dexamination of interestingness measures in pattern mining a unified framework.

Modeling Massive RFID Data Sets A Gateway%2DBased Movement Graph Approach.

The Inverse Classification Problem.
We consider the inverse problem in classification systems described as follows. Given a set of prototype cases representing a set of categories, a similarity function, and a new case classified in some category, find the cost minimizing changes to the attribute values such that the case is reclassified as a member of a (different) preferred category. The problem is “inverse ” because the usual mapping is from a case to its unknown category. The increased application of classification systems in business suggests that this inverse problem can be of significant benefit to decision-makers as a form of sensitivity analysis. Analytic approaches to this inverse problem are difficult to formulate as the constraints are either not available or difficult to determine. To investigate this inverse problem, we develop several genetic algorithms and study their performance as problem difficulty increases. We develop a real genetic algorithm with feasibility control, a traditional binary genetic algorithm, and a steepest ascent hill-climbing algorithm. In a series of simulation experiments, we compare the performance of these algorithms to the optimal solution as the problem difficulty increases (more attributes and classes). In addition, we analyze certain algorithm effects (level of feasibility control, operator design, and fitness function) to determine the best approach. Our results indicate the viability of the real genetic algorithm and the importance of feasibility control as the problem difficulty increases.
On Graph Query Optimization in Large Networks.
The dramatic proliferation of sophisticated networks has resulted in a growing need for supporting effective querying and mining methods over such large-scale graph-structured data. At the core of many advanced network operations lies a common and critical graph query primitive: how to search graph structures efficiently within a large network? Unfortunately, the graph query is hard due to the NP-complete nature of subgraph isomorphism. It becomes even challenging when the network examined is large and diverse. In this paper, we present a high performance graph indexing mechanism, SPath, to address the graph query problem on large networks. SPath leverages decomposed shortest paths around vertex neighborhood as basic indexing units, which prove to be both effective in graph search space pruning and highly scalable in index construction and deployment. Via SPath, a graph query is processed and optimized beyond the traditional vertex-at-a-time fashion to a more efficient path-at-a-time way: the query is first decomposed to a set of shortest paths, among which a subset of candidates with good selectivity is picked by a query plan optimizer; Candidate paths are further joined together to help recover the query graph to finalize the graph query processing. We evaluate SPath with the state-of-the-art GraphQL on both real and synthetic data sets. Our experimental studies demonstrate the effectiveness and scalability of SPath, which proves to be a more practical and efficient indexing method in addressing graph queries on large networks. 1.
Swarm Mining Relaxed Temporal Moving Object Clusters.
Recent improvements in positioning technology make massive moving object data widely available. One important analysis is to find the moving objects that travel together. Existing methods put a strong constraint in defining moving object cluster, that they require the moving objects to stick together for consecutive timestamps. Our key observation is that the moving objects in a cluster may actually diverge temporarily and congregate at certain timestamps. Motivatedbythis, wepropose theconceptofswarm which capturesthemovingobjectsthatmovewithinarbitraryshape of clusters for certain timestamps that are possibly nonconsecutive. The goal of our paper is to find all discriminative swarms, namely closed swarm. While the search space for closed swarms is prohibitively huge, we design a method, ObjectGrowth, to efficiently retrieve the answer. In ObjectGrowth, two effective pruning strategies are proposed to greatly reduce the search space and a novel closure checking rule is developed to report closed swarms on-thefly. Empirical studies on the real data as well as large synthetic data demonstrate the effectiveness and efficiency of our methods. 1.
Survey on social tagging techniques.

Discriminative frequent subgraph mining with optimality guarantees.

VideoMule a consensus learning approach to multi%2Dlabel classification from noisy user%2Dgenerated videos.

Mining Heterogeneous Information Networks by Exploring the Power of Links.


P%2DRank a comprehensive structural similarity measure over information networks.


Mining Heterogeneous Information Networks by Exploring the Power of Links.

CHRONICLE A Two%2DStage Density%2DBased Clustering Algorithm for Dynamic Networks.

Subspace Discovery for Promotion A Cell Clustering Approach.

Integrating Novel Class Detection with Classification for Concept%2DDrifting Data Streams.

Scalable OLAP and mining of information networks.

RankClus integrating clustering with ranking for heterogeneous information network analysis.

Real%2DTime Knowledge Discovery and Dissemination for Intelligence Analysis.
This paper describes the issues and challenges for real-time knowledge discovery and then discusses approaches and challenges for real-time data mining and stream mining. Our goal is to extract accurate information to support the emergency responder, the war fighter, as well as the intelligence analyst in a timely manner. 
Modeling Probabilistic Measurement Correlations for Problem Determination in Large%2DScale Distributed Systems.

Efficient Mining of Closed Repetitive Gapped Subsequences from a Sequence Database.

iTopicModel Information Network%2DIntegrated Topic Modeling.

Filtering and Refinement A Two%2DStage Approach for Efficient and Effective Anomaly Detection.

Parallel PathFinder Algorithms for Mining Structures from Graphs.

Mining Personal Image Collection for Social Group Suggestion.

Locality Preserving Nonnegative Matrix Factorization.
Matrix factorization techniques have been frequently applied in information processing tasks. Among them, Non-negative Matrix Factorization (NMF) have received considerable attentions due to its psychological and physiological interpretation of naturally occurring data whose representation may be parts-based in human brain. On the other hand, from geometric perspective the data is usually sampled from a low dimensional manifold embedded in high dimensional ambient space. One hopes then to find a compact representation which uncovers the hidden topics and simultaneously respects the intrinsic geometric structure. In this paper, we propose a novel algorithm, called Locality Preserving Non-negative Matrix Factorization (LPNMF), for this purpose. For two data points, we use KL-divergence to evaluate their similarity on the hidden topics. The optimal maps are obtained such that the feature values on hidden topics are restricted to be non-negative and vary smoothly along the geodesics of the data manifold. Our empirical study shows the encouraging results of the proposed algorithm in comparisons to the state-ofthe-art algorithms on two large high-dimensional databases. 1
Assured Information Sharing Life Cycle.

Heterogeneous source consensus learning via decision propagation and negotiation.
Nowadays, enormous amounts of data are continuously generated not only in massive scale, but also from different, sometimes conflicting, views. Therefore, it is important to consolidate different concepts for intelligent decision making. For example, to predict the research areas of some people, the best results are usually achieved by combining and consolidating predictions obtained from the publication network, co-authorship network and the textual content of their publications. Multiple supervised and unsupervised hypotheses can be drawn from these information sources, and negotiating their differences and consolidating decisions usually yields a much more accurate model due to the diversity and heterogeneity of these models. In this paper, we address the problem of “consensus learning ” among competing hypotheses, which either rely on outside knowledge (supervised learning) or internal structure (unsupervised clustering). We argue that consensus learning is an NP-hard problem and thus propose to solve it by an efficient heuristic method. We construct a belief graph to first propagate predictions from supervised models to the unsupervised, and then negotiate and reach consensus among them. Their final decision is further consolidated by calculating each model’s weight based on its degree of consistency with other models. Experiments are conducted on 20 Newsgroups data, Cora research papers, DBLP author-conference network, and Yahoo! Movies datasets, and the results show that the proposed method improves the classification accuracy and the clustering quality measure (NMI) over the best base model by up to 10%. Furthermore, it runs in time proportional to the number of instances, which is very efficient for large-scale data sets.
Classification of software behaviors for failure detection a discriminative pattern mining approach.

Ranking%2Dbased clustering of heterogeneous information networks with star network schema.


Exploring social tagging graph for web object classification.

A Multi%2Dpartition Multi%2Dchunk Ensemble Technique to Classify Concept%2DDrifting Data Streams.


Topic Cube Topic Modeling for OLAP on Multidimensional Text Databases.

GAD General Activity Detection for Fast Clustering on Large Data.

MLR%2DIndex An Index Structure for Fast and Scalable Similarity Search in High Dimensions.

Frequent Itemsets and Association Rules.

Pattern%2DGrowth Methods.
Mining frequent patterns from large databases plays an essential role in many data mining tasks and has broad applications. Most of the previously proposed methods adopt apriorilike candidate-generation-and-test approaches. However, those methods may encounter serious challenges when mining datasets with prolific patterns and/or long patterns. In this
Stream Mining.

Data Mining.

Exploring optimization of semantic relationship graph for multi%2Drelational Bayesian classification.

Top%2Ddown mining of frequent closed patterns from very high dimensional data.

Graph OLAP a multi%2Ddimensional framework for graph data analysis.

Promotion Analysis in Multi%2DDimensional Space.
Promotion is one of the key ingredients in marketing. It is often desirable to find merit in an object (e.g., product, person, organization, or service) and promote it in an appropriate community. In this paper, we propose a novel functionality, called promotion analysis through ranking, for promoting a given object by leveraging highly ranked results. Since the object may not be highly ranked in the global space, our goal is to discover promotive subspaces in which the object becomes prominent. To achieve this goal, the notion of promotiveness is formulated. We show that this functionality is practical and useful in a wide variety of applications such as business intelligence. However, computing promotive subspaces is challenging due to the explosion of search space and high aggregation cost. For efficient computation, we propose a PromoRank framework, and develop three efficient optimization techniques, namely subspace pruning, object pruning, and promotion cube, which are seamlessly integrated into the framework. Our empirical evaluation on two real data sets confirms the effectiveness of promotion analysis, and that our proposed algorithms significantly outperform baseline solutions. 1.
A Particle%2Dand%2DDensity Based Evolutionary Clustering Method for Dynamic Networks.
Recently, dynamic networks are attracting increasing interest due to their high potential in capturing natural and social phenomena over time. Discovery of evolutionary communities in dynamic networks has become a critical task. The previous evolutionary clustering methods usually adopt the temporal smoothness framework, which has a desirable feature of controlling the balance between temporal noise and true concept drift of communities. They, however, have some major drawbacks: (1) assuming only a fixed number of communities over time; and (2) not allowing arbitrary start/stop of community over time. The forming of new communities and dissolving of existing communities are very common phenomena in real dynamic networks. In this paper, we propose a new particle-and-density based evolutionary clustering method that efficiently discovers a variable number of communities of arbitrary forming and dissolving. We first model a dynamic network as a collection of lots of particles called nano-communities, and a community as a densely connected subset of particles, called a quasi l-clique-by-clique (shortly, l-KK). Each particle contains a small amount of information about the evolution of data or patterns, and the quasi l-KK s inherent in a given dynamic network provide us with guidance on how to find a variable number of communities of arbitrary forming and dissolving. We propose a density-based clustering method that efficiently finds temporally smoothed local clusters of high quality by using a cost embedding technique and optimal modularity. We also propose a mapping method based on information theory that makes sequences of smoothed local clusters as close as possible to data-inherent quasi l-KKs. The result of the mapping method allows us to easily identify the stage of each community among the three stages: evolving, forming, and dissolving. Experimental studies, by using various data sets, demonstrate that our method improves the clustering accuracy, and at the same time, the time performance by an order of magnitude compared with the current state-of-the art method.
Mining Graph Patterns Efficiently via Randomized Summaries.

iNextCube Information Network%2DEnhanced Text Cube.
Nowadays, most business, administration, and/or scientific databases contain both structured attributes and text attributes. We call a database that consists of both multidimensional structured data and narrative text data as multidimensional text database. Searching, OLAP, and mining such databases pose many research challenges. To enhance the power of data analysis, interesting entities and relationships can be extracted from such databases to derive heterogeneous information networks, which in turn will substantially increase the power and flexibility of data exploration in such databases. Based on our previous studies on TextCube [1], TopicCube [2], and information network analysis, such as RankClus [3] and NetClus [4], we construct iNextCube, an information-Network-enhanced text Cube. In this demo, we show the power of iNextCube in the search and analysis of two multidimensional text databases: (i) a DBLP-based CS bibliographic database, and (ii) an online news database. 1.
Topic modeling for OLAP on multidimensional text databases topic cube and its applications.

Sparse Projections over Graph.
Recent study has shown that canonical algorithms such as Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) can be obtained from graph based dimensionality reduction framework. However, these algorithms yield projective maps which are linear combination of all the original features. The results are difficult to be interpreted psychologically and physiologically. This paper presents a novel technique for learning a sparse projection over graphs. The data in the reduced subspace is represented as a linear combination of a subset of the most relevant features. Comparing to PCA and LDA, the results obtained by sparse projection are often easier to be interpreted. Our algorithm is based on a graph embedding model, which encodes the discriminating and geometrical structure in terms of the data affinity. Once the embedding results are obtained, we then apply regularized regression for learning a set of sparse basis functions. Specifically, by using a L1-norm regularizer (e.g. lasso), the sparse projections can be efficiently computed. Experimental results on two document databases demonstrate the effectiveness of our method.
On effective presentation of graph patterns a structural representative approach.
RESEARCH INTERESTS I am generally interested in data mining, data warehousing and database systems. My current research focuses on modeling, managing and analyzing large-scale graph and information network data.
Modeling hidden topics on document manifold.

Data mining for image%2Fvideo processing a promising research frontier.

P%2DCube Answering Preference Queries in Multi%2DDimensional Space.
 Many new applications that involve decision making need online (i.e., OLAP-styled) preference analysis with multidimensional boolean selections. Typical preference queries includes top-k queries and skyline queries. An analytical query often comes with a set of boolean predicates that constrain a target subset of data, which, may also vary incrementally by drilling/rolling operators. To efficiently support preference queries with multiple boolean predicates, neither boolean-thenpreference nor preference-then-boolean approach is satisfactory. To integrate boolean pruning and preference pruning in a unified framework, we propose signature, a new materialization measure for multi-dimensional group-bys. Based on this, we propose P-Cube (i.e., data cube for preference queries) and study its complete life cycle, including signature generation, compression, decomposition, incremental maintenance and usage for efficient on-line analytical query processing. We present a signature-based progressive algorithm that is able to simultaneously push boolean and preference constraints deep into the database search. Our performance study shows that the proposed method achieves at least one order of magnitude speed-up over existing approaches.  
Trajectory Outlier Detection A Partition%2Dand%2DDetect Framework.
Abstract — Outlier detection has been a popular data mining task. However, there is a lack of serious study on outlier detection for trajectory data. Even worse, an existing trajectory outlier detection algorithm has limited capability to detect outlying subtrajectories. In this paper, we propose a novel partition-and-detect framework for trajectory outlier detection, which partitions a trajectory into a set of line segments, and then, detects outlying line segments for trajectory outliers. The primary advantage of this framework is to detect outlying sub-trajectories from a trajectory database. Based on this partition-and-detect framework, we develop a trajectory outlier detection algorithm TRAOD. Our algorithm consists of two phases: partitioning and detection. For the first phase, we propose a two-level trajectory partitioning strategy that ensures both high quality and high efficiency. For the second phase, we present a hybrid of the distance-based and density-based approaches. Experimental results demonstrate that TRAOD correctly detects outlying sub-trajectories from real trajectory data. I.
Direct Discriminative Pattern Mining for Effective Classification.
Classification
Training Linear Discriminant Analysis in Linear Time.
Abstract—Linear Discriminant Analysis (LDA) has been a popular method for extracting features which preserve class separability. It has been widely used in many fields of information processing, such as machine learning, data mining, information retrieval, and pattern recognition. However, the computation of LDA involves dense matrices eigen-decomposition which can be computationally expensive both in time and memory. Specifically, LDA has O(mnt + t 3) time complexity and requires O(mn + mt + nt) memory, where m is the number of samples, n is the number of features and t = min(m, n). When both m and n are large, it is infeasible to apply LDA. In this paper, we propose a novel algorithm for discriminant analysis, called Spectral Regression Discriminant Analysis (SRDA). By using spectral graph analysis, SRDA casts discriminant analysis into a regression framework which facilitates both efficient computation and the use of regularization techniques. Our theoretical analysis shows that SRDA can be computed with O(ms) time and O(ms) memory, where s( ≤ n) is the average number of non-zero features in each sample. Extensive experimental results on four real world data sets demonstrate the effectiveness and efficiency of our algorithm. I.
Graph OLAP Towards Online Analytical Processing on Graphs.
RESEARCH INTERESTS I am generally interested in data mining, data warehousing and database systems. My current research focuses on modeling, managing and analyzing large-scale graph and information network data.
Non%2Dnegative Matrix Factorization on Manifold.
Recently Non-negative Matrix Factorization (NMF) has received a lot of attentions in information retrieval, computer vision and pattern recognition. NMF aims to find two non-negative matrices whose product can well approximate the original matrix. The sizes of these two matrices are usually smaller than the original matrix. This results in a compressed version of the original data matrix. The solution of NMF yields a natural parts-based representation for the data. When NMF is applied for data representation, a major disadvantage is that it fails to consider the geometric structure in the data. In this paper, we develop a graph based approach for parts-based data representation in order to overcome this limitation. We construct an affinity graph to encode the geometrical information and seek a matrix factorization which respects the graph structure. We demonstrate the success of this novel algorithm by applying it on real world problems. 1.
Text Cube Computing IR Measures for Multidimensional Text Database Analysis.

A Practical Approach to Classify Evolving Data Streams Training with Limited Amount of Labeled Data.

Stream Sequential Pattern Mining with Precise Error Bounds.

Exploring the Power of Heuristics and Links in Multi%2Drelational Data Mining.

Direct mining of discriminative and essential frequent patterns via model%2Dbased search tree.

Knowledge transfer via multiple model local structure mapping.
The effectiveness of knowledge transfer using classification algorithms depends on the difference between the distribution that generates the training examples and the one from which test examples are to be drawn. The task can be especially difficult when the training examples are from one or several domains different from the test domain. In this paper, we propose a locally weighted ensemble framework to combine multiple models for transfer learning, where the weights are dynamically assigned according to a model’s predictive power on each test example. It can integrate the advantages of various learning algorithms and the labeled information from multiple training domains into one unified classification model, which can then be applied on a different domain. Importantly, different from many previously proposed methods, none of the base learning method is required to be specifically designed for transfer learning. We show the optimality of a locally weighted ensemble framework as a general approach to combine multiple models for domain transfer. We then propose an implementation of the local weight assignments by mapping the structures of a model onto the structures of the test domain, and then weighting each model locally according to its consistency with the neighborhood structure around the test example. Experimental results on text classification, spam filtering and intrusion detection data sets demonstrate significant improvements in classification accuracy gained by the framework. On a transfer learning task of newsgroup message categorization, the proposed locally weighted ensemble framework achieves 97 % accuracy when the best single model predicts correctly only on 73 % of the test examples. In summary, the improvement in accuracy is over 10 % and up to 30 % across different problems.
Mining preferences from superior and inferior examples.
Mining user preferences plays a critical role in many important applications such as customer relationship management (CRM), product and service recommendation, and marketing campaigns. In this paper, we identify an interesting and practical problem of mining user preferences: in a multidimensional space where the user preferences on some categorical attributes are unknown, from some superior and inferior examples provided by a user, can we learn about the user’s preferences on those categorical attributes? We model the problem systematically and show that mining user preferences from superior and inferior examples is challenging. Although the problem has great potential in practice, to the best of our knowledge, it has not been explored systematically before. As the first attempt to tackle the problem, we propose a greedy method and show that our method is practical using real data sets and synthetic data sets.
Data Mining for Diagnostic Debugging in Sensor Networks Preliminary Evidence and Lessons Learned.

SpaRClus Spatial Relationship Pattern%2DBased Hierarchial Clustering.

CISpan Comprehensive Incremental Mining Algorithms of Closed Sequential Patterns for Multi%2DVersional Software Mining.
Recently, frequent sequential pattern mining algorithms have been widely used in software engineering field to mine various source code or specification patterns. In practice, software evolves from one version to another in its life span. The effort of mining frequent sequential patterns across multiple versions of a software can be substantially reduced by efficient incremental mining. This problem is challenging in this domain since the databases are usually updated in all kinds of manners including insertion, various modifications as well as removal of sequences. Also, different mining tools may have various mining constraints, such as low minimum support. None of the existing work can be applied effectively due to various limitations of such work. For example, our recent work, IncSpan, failed solving the problem because it could neither handle low minimum support nor removal of
BibNetMiner mining bibliographic information networks.

Mining significant graph patterns by leap search.

Sampling cube a framework for statistical olap over sampling data.
Sampling is a popular method of data collection when it is impossible or too costly to reach the entire population. For example, television show ratings in the United States are gathered from a sample of roughly 5,000 households. To use the results effectively, the samples are further partitioned in a multidimensional space based on multiple attribute values. This naturally leads to the desirability of OLAP (Online Analytical Processing) over sampling data. However, unlike traditional data, sampling data is inherently uncertain, i.e., not representing the full data in the population. Thus, it is desirable to return not only query results but also the confidence intervals indicating the reliability of the results. Moreover, a certain segment in a multidimensional space may contain none or too few samples. This requires some additional analysis to return trustable results. In this paper we propose a Sampling Cube framework, which efficiently calculates confidence intervals for any multidimensional query and uses the OLAP structure to group similar segments to increase sampling size when needed. Further, to handle high dimensional data, a Sampling Cube Shell method is proposed to effectively reduce the storage requirement while still preserving query result quality.
ARCube supporting ranking aggregate queries in partially materialized data cubes.
Supporting ranking queries in database systems has been a popular research topic recently. However, there is a lack of study on supporting ranking queries in data warehouses where ranking is on multidimensional aggregates instead of on measures of base facts. To address this problem, we propose a query execution model to answer different types of ranking aggregate queries based on a unified, partial cube structure, ARCube. The query execution model follows a candidate generation and verification framework, where the most promising candidate cells are generated using a set of high-level guiding cells. We also identify a bounding principle for effective pruning: once a guiding cell is pruned, all of its children candidate cells can be pruned. We further address the problem of efficient online candidate aggregation and verification by developing a chunk-based execution model to verify a bulk of candidates within a bounded memory buffer. Our extensive performance study shows that the new framework not only leads to an order of magnitude performance improvements over the state-of-the-art method, but also is much more flexible in terms of the types of ranking aggregate queries supported.
Dustminer troubleshooting interactive complexity bugs in sensor networks.

PerRank Personalized Rank Retrieval with Categorical and Numerical Attributes.

OLAP%2C Spatial.

Anomaly Detection in Moving Object.
With recent advances in sensory and mobile computing technology, enormous amounts of data about moving objects are being collected. One important application with such data is automated identification of suspicious movements. Due to the sheer volume of data associated with moving objects, it is challenging to develop a method that can efficiently and effectively detect anomalies. The problem is exacerbated by the fact that anomalies may occur at arbitrary levels of abstraction and be associated with multiple granularity of spatiotemporal features. In this study, we propose a new framework named ROAM (Rule- and Motif-based Anomaly Detection in Moving Objects). In ROAM, object trajectories are expressed using discrete pattern fragments called motifs. Associated features are extracted to form a hierarchical feature space, which facilitates a multi-resolution view of the data. We also develop a general-purpose, rulebased classifier which explores the structured feature space and learns effective rules at multiple levels of granularity. We implemented ROAM and tested its components under a variety of conditions. Our experiments show that the system is efficient and effective at detecting abnormal moving objects. 1
Approximate Frequent Itemset Mining In the Presence of Random Noise.

Classifying Data Streams with Skewed Class Distributions and Concept Drifts.

SRDA An Efficient Algorithm for Large%2DScale Discriminant Analysis.
Abstract—Linear Discriminant Analysis (LDA) has been a popular method for extracting features that preserves class separability. The projection functions of LDA are commonly obtained by maximizing the between-class covariance and simultaneously minimizing the within-class covariance. It has been widely used in many fields of information processing, such as machine learning, data mining, information retrieval, and pattern recognition. However, the computation of LDA involves dense matrices eigendecomposition, which can be computationally expensive in both time and memory. Specifically, LDA has Oðmnt þ t3Þ time complexity and requires Oðmn þ mt þ ntÞ memory, where m is the number of samples, n is the number of features, and t  minðm; nÞ. When both m and n are large, it is infeasible to apply LDA. In this paper, we propose a novel algorithm for discriminant analysis, called Spectral Regression Discriminant Analysis (SRDA). By using spectral graph analysis, SRDA casts discriminant analysis into a regression framework that facilitates both efficient computation and the use of regularization techniques. Specifically, SRDA only needs to solve a set of regularized least squares problems, and there is no eigenvector computation involved, which is a huge save of both time and memory. Our theoretical analysis shows that SRDA can be computed with OðmsÞ time and OðmsÞ memory, where sð nÞ is the average number of nonzero features in each sample. Extensive experimental results on four real-world data sets demonstrate the effectiveness and efficiency of our algorithm. Index Terms—Linear Discriminant Analysis, spectral regression, dimensionality reduction. Ç 1
Learning a Maximum Margin Subspace for Image Retrieval.
Abstract—One of the fundamental problems in Content-Based Image Retrieval (CBIR) has been the gap between low-level visual features and high-level semantic concepts. To narrow down this gap, relevance feedback is introduced into image retrieval. With the user-provided information, a classifier can be learned to distinguish between positive and negative examples. However, in real-world applications, the number of user feedbacks is usually too small compared to the dimensionality of the image space. In order to cope with the high dimensionality, we propose a novel semisupervised method for dimensionality reduction called Maximum Margin Projection (MMP). MMP aims at maximizing the margin between positive and negative examples at each local neighborhood. Different from traditional dimensionality reduction algorithms such as Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA), which effectively see only the global euclidean structure, MMP is designed for discovering the local manifold structure. Therefore, MMP is likely to be more suitable for image retrieval, where nearest neighbor search is usually involved. After projecting the images into a lower dimensional subspace, the relevant images get closer to the query image; thus, the retrieval performance can be enhanced. The experimental results on Corel image database demonstrate the effectiveness of our proposed algorithm. Index Terms—Multimedia information systems, image retrieval, relevance feedback, dimensionality reduction.
A Systematic Study of Failure Proximity.

Truth Discovery with Multiple Conflicting Information Providers on the Web.
The world-wide web has become the most important information source for most of us. Unfortunately, there is no guarantee for the correctness of information on the web. Moreover, different web sites often provide conflicting information on a subject, such as different specifications for the same product. In this paper we propose a new problem called Veracity, i.e., conformity to truth, which studies how to find true facts from a large amount of conflicting information on many subjects that is provided by various web sites. We design a general framework for the Veracity problem, and invent an algorithm called TruthFinder, which utilizes the relationships between web sites and their information, i.e., a web site is trustworthy if it provides many pieces of true information, and a piece of information is likely to be true if it is provided by many trustworthy web sites. Our experiments show that TruthFinder successfully finds true facts among conflicting information, and identifies trustworthy web sites better than the popular search engines.
A Systematic Study of Failure Proximity.

Efficiently Identifying Max%2DGap Clusters in Pairwise Genome Comparison.

On Having Search Engines Deliver Hierarchies of Web Pages.
There is large room for improving the usefulness of today’s Internet search engines. There are various ways. One of the ways is, when given a sub-directory (subWeb) of a Web site in a certain domain, to automatically retrieve, or mine, corresponding subdirectories of other Web sites in a similar domain. In this article, we outline a methodology for doing this. 1
TraClass trajectory classification using hierarchical region%2Dbased and trajectory%2Dbased clustering.
Trajectory classification, i.e., model construction for predicting the class labels of moving objects based on their trajectories and other features, has many important, real-world applications. A number of methods have been reported in the literature, but due to using the shapes of whole trajectories for classification, they have limited classification capability when discriminative features appear at parts of trajectories or are not relevant to the shapes of trajectories. These situations are often observed in long trajectories spreading over large geographic areas. Since an essential task for effective classification is generating discriminative features, a feature generation framework TraClass for trajectory data is proposed in this paper, which generates a hierarchy of features by partitioning trajectories and exploring two types of clustering: (1) region-based and (2) trajectory-based. The former captures the higher-level region-based features without using movement patterns, whereas the latter captures the lower-level trajectory-based features using movement patterns. The proposed framework overcomes the limitations of the previous studies because trajectory partitioning makes discriminative parts of trajectories identifiable, and the two types of clustering collaborate to find features of both regions and sub-trajectories. Experimental results demonstrate that TraClass generates high-quality features and achieves high classification accuracy from real trajectory data. 1.
Isometric Projection.
Recently the problem of dimensionality reduction has received a lot of interests in many fields of information processing, including data mining, information retrieval, and pattern recognition. We consider the case where data is sampled from a low dimensional manifold which is embedded in high dimensional Euclidean space. The most popular manifold learning algorithms include Locally Linear Embedding, ISOMAP, and Laplacian Eigenmap. However, these algorithms are nonlinear and only provide the embedding results of training samples. In this paper, we propose a novel linear dimensionality reduction algorithm, called Isometric Projection. Isometric Projection constructs a weighted data graph where the weights are discrete approximations of the geodesic distances on the data manifold. A linear subspace is then obtained by preserving the pairwise distances. Our algorithm can be performed in either original space or reproducing kernel Hilbert space, which leads to Kernel Isometric Projection. In this way, Isometric Projection can be defined everywhere. Comparing to Principal Component Analysis (PCA) which is widely used in data processing, our algorithm is more capable of discovering the intrinsic geometrical structure. Specially, PCA is optimal only when the data space is linear, while our algorithm has no such assumption and therefore can handle more complex data space. We present experimental results of the algorithm applied to synthetic data set as well as real life data. These examples illustrate the effectiveness of the proposed method. 1
Spectral regression a unified subspace learning framework for content%2Dbased image retrieval.
Relevance feedback is a well established and effective framework for narrowing down the gap between low-level visual features and high-level semantic concepts in content-based image retrieval. In most of traditional implementations of relevance feedback, a distance metric or a classifier is usually learned from user’s provided negative and positive examples. However, due to the limitation of the user’s feedbacks and the high dimensionality of the feature space, one is often confront with the issue of the curse of the dimensionality. Recently, several researchers have considered manifold ways to address this issue, such as Locality Preserving Projections, Augmented Relation Embedding, and Semantic Subspace Projection. In this paper, by using techniques from spectral graph embedding and regression, we propose a unified framework, called spectral regression, for learning an image subspace. This framework facilitates the analysis of the differences and connections between the algorithms mentioned above. And more crucially, it provides much faster computation and therefore makes the retrieval system capable of responding to the user’s query more efficiently.
Exploring the Power of Links in Data Mining.

Spectral Regression for Efficient Regularized Subspace Learning.
Subspace learning based face recognition methods have attracted considerable interests in recent years, including Principal Component Analysis (PCA), Linear Discriminant Analysis (LDA), Locality Preserving Projection (LPP), Neighborhood Preserving Embedding (NPE) and Marginal Fisher Analysis (MFA). However, a disadvantage of all these approaches is that their computations involve eigendecomposition of dense matrices which is expensive in both time and memory. In this paper, we propose a novel dimensionality reduction framework, called Spectral Regression (SR), for efficient regularized subspace learning. SR casts the problem of learning the projective functions into a regression framework, which avoids eigen-decomposition of dense matrices. Also, with the regression based framework, different kinds of regularizers can be naturally incorporated into our algorithm which makes it more flexible. Computational analysis shows that SR has only linear-time complexity which is a huge speed up comparing to the cubic-time complexity of the ordinary approaches. Experimental results on face recognition demonstrate the effectiveness and efficiency of our method. 1.
Regularized locality preserving indexing via spectral regression.
We consider the problem of document indexing and representation. Recently, Locality Preserving Indexing (LPI) was proposed for learning a compact document subspace. Different from Latent Semantic Indexing (LSI) which is optimal in the sense of global Euclidean structure, LPI is optimal in the sense of local manifold structure. However, LPI is not efficient in time and memory which makes it difficult to be applied to very large data set. Specifically, the computation of LPI involves eigen-decompositions of two dense matrices which is expensive. In this paper, we propose a new algorithm called Regularized Locality Preserving Indexing (RLPI). Benefit from recent progresses on spectral graph analysis, we cast the original LPI algorithm into a regression framework which enable us to avoid eigen-decomposition of dense matrices. Also, with the regression based framework, different kinds of regularizers can be naturally incorporated into our algorithm which makes it more flexible. Extensive experimental results show that RLPI obtains similar or better results comparing to LPI and it is significantly faster, which makes it an efficient and effective data preprocessing method for large scale text clustering, classification and retrieval.
Learning a Spatially Smooth Subspace for Face Recognition.
Subspace learning based face recognition methods have attracted considerable interests in recently years, including
Semi%2Dsupervised Discriminant Analysis.
Linear Discriminant Analysis (LDA) has been a popular method for extracting features which preserve class separability. The projection vectors are commonly obtained by maximizing the between class covariance and simultaneously minimizing the within class covariance. In practice, when there is no sufficient training samples, the covariance matrix of each class may not be accurately estimated. In this paper, we propose a novel method, called Semisupervised Discriminant Analysis (SDA), which makes use of both labeled and unlabeled samples. The labeled data points are used to maximize the separability between different classes and the unlabeled data points are used to estimate the intrinsic geometric structure of the data. Specifically, we aim to learn a discriminant function which is as smooth as possible on the data manifold. Experimental results on single training image face recognition and relevance feedback image retrieval demonstrate the effectiveness of our algorithm. 1.
Spectral Regression for Efficient Regularized Subspace Learning.
Subspace learning based face recognition methods have attracted considerable interests in recent years, including Principal Component Analysis (PCA), Linear Discriminant Analysis (LDA), Locality Preserving Projection (LPP), Neighborhood Preserving Embedding (NPE) and Marginal Fisher Analysis (MFA). However, a disadvantage of all these approaches is that their computations involve eigendecomposition of dense matrices which is expensive in both time and memory. In this paper, we propose a novel dimensionality reduction framework, called Spectral Regression (SR), for efficient regularized subspace learning. SR casts the problem of learning the projective functions into a regression framework, which avoids eigen-decomposition of dense matrices. Also, with the regression based framework, different kinds of regularizers can be naturally incorporated into our algorithm which makes it more flexible. Computational analysis shows that SR has only linear-time complexity which is a huge speed up comparing to the cubic-time complexity of the ordinary approaches. Experimental results on face recognition demonstrate the effectiveness and efficiency of our method. 1.
Cost%2DConscious Cleaning of Massive RFID Data Sets.
Efficient and accurate data cleaning is an essential task for the successful deployment of RFID systems. Although important advances have been made in tag detection rates, it is still common to see a large number of lost readings due to radio frequency (RF) interference and tag-reader configurations. Existing cleaning techniques have focused on the development of accurate methods that work well under a wide set of conditions, but have disregarded the very high cost of cleaning in a real application that may have thousands of readers and millions of tags. In this paper, we propose a cleaning framework that takes an RFID data set and a collection of cleaning methods, with associated costs, and induces a cleaning plan that optimizes the overall accuracyadjusted cleaning costs by determining the conditions under which inexpensive methods are appropriate, and those when more expensive methods are absolutely necessary. 1
The Multi%2DRelational Skyline Operator.
Most of the existing work on skyline query has been extensively used in decision support, recommending systems etc, and mainly focuses on the efficiency issue for a single table. However the data retrieved by users for the targeting skylines may often be stored in multiple tables, thus require to perform join operations among tables. As a result, the cost on computing skylines on the joined table will be increased dramatically due to its potentially increasing cardinality and dimensionality. In this paper, we systematically study the skyline operator on multi-relational databases, and propose solutions aiming to seamlessly integrating state-of-the-art join methods into skyline computation. Our experiments not only demonstrate that the proposed methods are efficient, but also show the promising applicability of extending skyline operator to other typical database operators such as join and aggregates. 1
Mining Colossal Frequent Patterns by Core Pattern Fusion.
Extensive research for frequent-pattern mining in the past decade has brought forth a number of pattern mining algorithms that are both effective and efficient. However, the existing frequent-pattern mining algorithms encounter challenges at mining rather large patterns, called colossal frequent patterns, in the presence of an explosive number of frequent patterns. Colossal patterns are critical to many applications, especially in domains like bioinformatics. In this study, we investigate a novel mining approach called Pattern-Fusion to efficiently find a good approximation to the colossal patterns. With Pattern-Fusion, a colossal pattern is discovered by fusing its small core patterns in one step, whereas the incremental pattern-growth mining strategies, such as those adopted in Apriori and FP-growth, have to examine a large number of mid-sized ones. This property distinguishes Pattern-Fusion from all the existing frequent pattern mining approaches and draws a new mining methodology. Our empirical studies show that, in cases where current mining algorithms cannot proceed, Pattern-Fusion is able to mine a result set which is a close enough approximation to the complete set of the colossal patterns, under a quality evaluation model proposed in this paper. 1
Discriminative Frequent Pattern Analysis for Effective Classification.
The application of frequent patterns in classification appeared in sporadic studies and achieved initial success in the classification of relational data, text documents and graphs. In this paper, we conduct a systematic exploration of frequent pattern-based classification, and provide solid reasons supporting this methodology. It was well known that feature combinations (patterns) could capture more underlying semantics than single features. However, inclusion of infrequent patterns may not significantly improve the accuracy due to their limited predictive power. By building a connection between pattern frequency and discriminative measures such as information gain and Fisher score, we develop a strategy to set minimum support in frequent pattern mining for generating useful patterns. Based on this strategy, coupled with a proposed feature selection algorithm, discriminative frequent patterns can be generated for building high quality classifiers. We demonstrate that the frequent pattern-based classification framework can achieve good scalability and high accuracy in classifying large datasets. Empirical studies indicate that significant improvement in classification accuracy is achieved (up to 12 % in UCI datasets) using the so-selected discriminative frequent patterns. 1.
Integrating OLAP and Ranking The Ranking%2DCube Methodology.

On Appropriate Assumptions to Mine Data Streams Analysis and Practice.
Recent years have witnessed an increasing number of studies in stream mining, which aim at building an accurate model for continuously arriving data. Somehow most existing work makes the implicit assumption that the training data and the yet-to-come testing data are always sampled from the “same distribution”, and yet this “same distribution” evolves over time. We demonstrate that this may not be true, and one actually may never know either “how ” or “when ” the distribution changes. Thus, a model that fits well on the observed distribution can have unsatisfactory accuracy on the incoming data. Practically, one can just assume the bare minimum that learning from observed data is better than both random guessing and always predicting exactly the same class label. Importantly, we formally and
Efficient Kernel Discriminant Analysis via Spectral Regression.
Linear Discriminant Analysis (LDA) has been a popular method for extracting features which preserve class separability. The projection vectors are commonly obtained by maximizing the between class covariance and simultaneously minimizing the within class covariance. LDA can be performed either in the original input space or in the reproducing kernel Hilbert space (RKHS) into which data points are mapped, which leads to Kernel Discriminant Analysis (KDA). When the data are highly nonlinear distributed, KDA can achieve better performance than LDA. However, computing the projective functions in KDA involves eigen-decomposition of kernel matrix, which is very expensive when a large number of training samples exist. In this paper, we present a new algorithm for kernel discriminant analysis, called Spectral Regression Kernel Discriminant Analysis (SRKDA). By using spectral graph analysis, SRKDA casts discriminant analysis into a regression framework which facilitates both efficient computation and the use of regularization techniques. Specifically, SRKDA only needs to solve a set of regularized regression problems and there is no eigenvector computation involved, which is a huge save of computational cost. Our computational analysis shows that SRKDA is 27 times faster than the ordinary KDA. Moreover, the new formulation makes it very easy to develop incremental version of the algorithm which can fully utilize the computational results of the existing training samples. Experiments on face recognition demonstrate the effectiveness and efficiency of the proposed algorithm. 1.
gApprox Mining Frequent Approximate Patterns from a Massive Network.
Recently, there arise a large number of graphs with massive sizes and complex structures in many new applications, such as biological networks, social networks, and the Web, demanding powerful data mining methods. Due to inherent noise or data diversity, it is crucial to address the issue of approximation, if one wants to mine patterns that are potentially interesting with tolerable variations. In this paper, we investigate the problem of mining frequent approximate patterns from a massive network and propose a method called gApprox. gApprox not only finds approximate network patterns, which is the key for many knowledge discovery applications on structural data, but also enriches the library of graph mining methodologies by introducing several novel techniques such as: (1) a complete and redundancy-free strategy to explore the new pattern space faced by gApprox; and (2) transform “frequent in an approximate sense ” into an anti-monotonic constraint so that it can be pushed deep into the mining process. Systematic empirical studies on both real and synthetic data sets show that frequent approximate patterns mined from the worm protein-protein interaction network are biologically interesting and gApprox is both effective and efficient. 1
Spectral Regression A Unified Approach for Sparse Subspace Learning.
Recently the problem of dimensionality reduction (or, subspace learning) has received a lot of interests in many fields of information processing, including data mining, information retrieval, and pattern recognition. Some popular methods include Principal Component Analysis (PCA), Linear Discriminant Analysis (LDA) and Locality Preserving Projection (LPP). However, a disadvantage of all these approaches is that the learned projective functions are linear combinations of all the original features, thus it is often difficult to interpret the results. In this paper, we propose a novel dimensionality reduction framework, called Unified Sparse Subspace Learning (USSL), for learning sparse projections. USSL casts the problem of learning the projective functions into a regression framework, which facilitates the use of different kinds of regularizers. By using a L1-norm regularizer (lasso), the sparse projections can be efficiently computed. Experimental results on real world classification and clustering problems demonstrate the effectiveness of our method. 1.
Efficient Discovery of Frequent Approximate Sequential Patterns.
We propose an efficient algorithm for mining frequent approximate sequential patterns under the Hamming distance model. Our algorithm gains its efficiency by adopting a “break-down-and-build-up ” methodology. The “breakdown” is based on the observation that all occurrences of a frequent pattern can be classified into groups, which we call strands. We developed efficient algorithms to quickly mine out all strands by iterative growth. In the “build-up” stage, these strands are grouped up to form the support sets from which all approximate patterns would be identified. A salient feature of our algorithm is its ability to grow the frequent patterns by iteratively assembling building blocks of significant sizes in a local search fashion. By avoiding incremental growth and global search, we achieve greater efficiency without losing the completeness of the mining result. Our experimental studies demonstrate that our algorithm is efficient in mining globally repeating approximate sequential patterns that would have been missed by existing methods. 1
Indexing Noncrashing Failures A Dynamic Program Slicing%2DBased Approach.

Locality Sensitive Discriminant Analysis.
Linear Discriminant Analysis (LDA) is a popular data-analytic tool for studying the class relationship between data points. A major disadvantage of LDA is that it fails to discover the local geometrical structure of the data manifold. In this paper, we introduce a novel linear algorithm for discriminant analysis, called Locality Sensitive Discriminant Analysis (LSDA). When there is no sufficient training samples, local structure is generally more important than global structure for discriminant analysis. By discovering the local manifold structure, LSDA finds a projection which maximizes the margin between data points from different classes at each local area. Specifically, the data points are mapped into a subspace in which the nearby points with the same label are close to each other while the nearby points with different labels are far apart. Experiments carried out on several standard face databases show a clear improvement over the results of LDA-based recognition.
Mining%2C Indexing%2C and Searching Graphs in Large Data Sets.

Truth discovery with multiple conflicting information providers on the web.
The world-wide web has become the most important information source for most of us. Unfortunately, there is no guarantee for the correctness of information on the web. Moreover, different web sites often provide conflicting information on a subject, such as different specifications for the same product. In this paper we propose a new problem called Veracity, i.e., conformity to truth, which studies how to find true facts from a large amount of conflicting information on many subjects that is provided by various web sites. We design a general framework for the Veracity problem, and invent an algorithm called TruthFinder, which utilizes the relationships between web sites and their information, i.e., a web site is trustworthy if it provides many pieces of true information, and a piece of information is likely to be true if it is provided by many trustworthy web sites. Our experiments show that TruthFinder successfully finds true facts among conflicting information, and identifies trustworthy web sites better than the popular search engines.
Mining%2C Indexing%2C and Searching Graphs in Large Data Sets.

Regularized regression on image manifold for retrieval.
Recently, there have been considerable interests in geometric-based methods for image retrieval. These methods consider the image space as a smooth manifold and apply manifold learning techniques to find a Euclidean embedding. Thus, the Euclidean distances in the embedding space can be used as approximations to the geodesic distances on the manifold. A main advantage of these methods is that the relevance feedbacks during retrieval can be naturally incorporated into the system as prior information. In this paper, we consider the retrieval problem as a classification problem on manifold. Instead of learning a distance measure, we aim to learn a classification function on the image manifold. Considering efficiency is a key issue in image retrieval, especially on the Web scale, we propose a novel approach for image retrieval on manifold. This approach is based on a regularized linear regression framework. The local manifold structure and user-provided relevance feedbacks are incorporated into the image retrieval system through a Locality Preserving Regularizer. Extensive experiments are carried out on a large image database which demonstrates the efficiency and effectiveness of the proposed approach.
Research Frontiers in Advanced Data Mining Technologies and Applications.

gPrune A Constraint Pushing Framework for Graph Pattern Mining.
Abstract. In graph mining applications, there has been an increasingly strong urge for imposing user-specified constraints on the mining results. However, unlike most traditional itemset constraints, structural constraints, such as density and diameter of a graph, are very hard to be pushed deep into the mining process. In this paper, we give the first comprehensive study on the pruning properties of both traditional and structural constraints aiming to reduce not only the pattern search space but the data search space as well. A new general framework, called gPrune, is proposed to incorporate all the constraints in such a way that they recursively reinforce each other through the entire mining process. A new concept, Pattern-inseparable Data-antimonotonicity, is proposed to handle the structural constraints unique in the context of graph, which, combined with known pruning properties, provides a comprehensive and unified classification framework for structural constraints. The exploration of these antimonotonicities in the context of graph pattern mining is a significant extension to the known classification of constraints, and deepens our understanding of the pruning properties of structural graph constraints. 1
Association Mining in Large Databases A Re%2Dexamination of Its Measures.
Abstract. In the literature of data mining and statistics, numerous interestingness measures have been proposed to disclose succinct object relationships of association patterns. However, it is still not clear when a measure is truly effective in large data sets. Recent studies have identified a critical property, null-(transaction) invariance, for measuring event associations in large data sets, but many existing measures do not have this property. We thus re-examine the null-invariant measures and find interestingly that they can be expressed as a generalized mathematical mean, and there exists a total ordering of them. This ordering provides insights into the underlying philosophy of the measures and helps us understand and select the proper measure for different applications. 1
A General Framework for Mining Concept%2DDrifting Data Streams with Skewed Distributions.
In recent years, there have been some interesting studies on predictive modeling in data streams. However, most such studies assume relatively balanced and stable data streams but cannot handle well rather skewed (e.g., few positives but lots of negatives) and stochastic distributions, which are typical in many data stream applications. In this paper, we propose a new approach to mine data streams by estimating reliable posterior probabilities using an ensemble of models to match the distribution over under-samples of negatives and repeated samples of positives. We formally show some interesting and important properties of the proposed framework, e.g., reliability of estimated probabilities on skewed positive class, accuracy of estimated probabilities, efficiency and scalability. Experiments are performed on several synthetic as well as real-world datasets with skewed distributions, and they demonstrate that our framework has substantial advantages over existing approaches in estimation reliability and predication accuracy. 1
ROAM Rule%2D and Motif%2DBased Anomaly Detection in Massive Moving Object Data Sets.
With recent advances in sensory and mobile computing technology, enormous amounts of data about moving objects are being collected. One important application with such data is automated identification of suspicious movements. Due to the sheer volume of data associated with moving objects, it is challenging to develop a method that can efficiently and effectively detect anomalies. The problem is exacerbated by the fact that anomalies may occur at arbitrary levels of abstraction and be associated with multiple granularity of spatiotemporal features. In this study, we propose a new framework named ROAM (Rule- and Motif-based Anomaly Detection in Moving Objects). In ROAM, object trajectories are expressed using discrete pattern fragments called motifs. Associated features are extracted to form a hierarchical feature space, which facilitates a multi-resolution view of the data. We also develop a general-purpose, rulebased classifier which explores the structured feature space and learns effective rules at multiple levels of granularity. We implemented ROAM and tested its components under a variety of conditions. Our experiments show that the system is efficient and effective at detecting abnormal moving objects. 1
Progressive and selective merge computing top%2Dk with ad%2Dhoc ranking functions.
The family of threshold algorithm (i.e., TA) has been widely studied for efficiently computing top-k queries. TA uses a sort-merge framework that assumes data lists are pre-sorted, and the ranking functions are monotone. However, in many database applications, attribute values are indexed by treestructured indices (e.g., B-tree, R-tree), and the ranking functions are not necessarily monotone. To answer top-k queries with ad-hoc ranking functions, this paper studies an index-merge paradigm that performs progressive search over the space of joint states composed by multiple index nodes. We address two challenges for efficient query processing. First, to minimize the search complexity, we present a doubleheap algorithm which supports not only progressive state search but also progressive state generation. Second, to avoid unnecessary disk access, we characterize a type of “empty-state ” that does not contribute to the final results, and propose a new materialization model, join-signature, to prune empty-states. Our performance study shows that the proposed method achieves one order of magnitude speed-up over baseline solutions.
Trajectory clustering a partition%2Dand%2Dgroup framework.
Existing trajectory clustering algorithms group similar trajectories as a whole, thus discovering common trajectories. Our key observation is that clustering trajectories as a whole could miss common sub-trajectories. Discovering common sub-trajectories is very useful in many applications, especially if we have regions of special interest for analysis. In this paper, we propose a new partition-and-group framework for clustering trajectories, which partitions a trajectory into a set of line segments, and then, groups similar line segments together into a cluster. The primary advantage of this framework is to discover common sub-trajectories from a trajectory database. Based on this partition-and-group framework, we develop a trajectory clustering algorithm TRA-CLUS. Our algorithm consists of two phases: partitioning and grouping. For the first phase, we present a formal trajectory partitioning algorithm using the minimum description length (MDL) principle. For the second phase, we present a density-based line-segment clustering algorithm. Experimental results demonstrate that TRACLUS correctly discovers common sub-trajectories from real trajectory data.
Finding frequent items in data streams using hierarchical information.

On Efficient Processing of Subspace Skyline Queries on High Dimensional Data.
Recent studies on efficiently answering subspace skyline queries can be separated into two approaches. The first focused on pre-materializing a set of skylines points in various subspaces while the second focus on dynamically answering the queries by using a set of anchors to prune off skyline points through spatial reasoning. Despite effort to compress the pre-materialized subspace skylines through removal of redundancy, the storage space for the first approach remain exponential in the number of dimensions. The query time for the second approach on the other hand also grow substantially for data with higher dimensionality where the pruning power of anchors become much weaker. In this paper, we propose methods for answering subspace skyline query on high dimensional data such that both prematerialization storage and query time can be moderated. We propose novel notions of maximal partial-dominating space, maximal partial-dominated space and the maximal equality space between pairs of skyline objects in the full space and use these concepts as the foundation for answering subspace skyline queries for high dimensional data. Query processing involves mostly simple pruning operations while skyline computation is done only on a small subset of candidate skyline points in the subspace. We also develop a random sampling method to compute the subspace skyline in an on-line fashion. Extensive experiments have been conducted and demonstrated the efficiency and effectiveness of our methods. 1
Traffic Density%2DBased Discovery of Hot Routes in Road Networks.
  Finding hot routes (traffic flow patterns) in a road network is an important problem. They are beneficial to city planners, police departments, real estate developers, and many others. Knowing the hot routes allows the city to better direct traffic or analyze congestion causes. In the past, this problem has largely been addressed with domain knowledge of city. But in recent years, detailed information about vehicles in the road network have become available. With the development and adoption of RFID and other location sensors, an enormous amount of moving object trajectories are being collected and can be used towards finding hot routes. This is a challenging problem due to the complex nature of the data. If objects traveled in organized clusters, it would be straightforward to use a clustering algorithm to find the hot routes. But, in the real world, objects move in unpredictable ways. Variations in speed, time, route, and other factors cause them to travel in rather fleeting “clusters. ” These properties make the problem difficult for a naive approach. To this end, we propose a new density-based algorithm named FlowScan. Instead of clustering the moving objects, road segments are clustered based on the density of common traffic they share. We implemented FlowScan and tested it under various conditions. Our experiments show that the system is both efficient and effective at discovering hot routes.  
DataScope Viewing Database Contents in Google Maps%27 Way.

Mining Approximate Top%2DK Subspace Anomalies in Multi%2DDimensional Time%2DSeries Data.
Market analysis is a representative data analysis process with many applications. In such an analysis, critical numerical measures, such as profit and sales, fluctuate over time and form time-series data. Moreover, the time series data correspond to market segments, which are described by a set of attributes, such as age, gender, education, income level, and product-category, that form a multi-dimensional structure. To better understand market dynamics and predict future trends, it is crucial to study the dynamics of time-series in multi-dimensional market segments. This is a topic that has been largely ignored in time series and data cube research. In this study, we examine the issues of anomaly detection in multi-dimensional time-series data. We propose timeseries data cube to capture the multi-dimensional space formed by the attribute structure. This facilitates the detection of anomalies based on expected values derived from higher level, “more general ” time-series. Anomaly detection in a time-series data cube poses computational challenges, especially for high-dimensional, large data sets. To this end, we also propose an efficient search algorithm to iteratively select subspaces in the original high-dimensional space and detect anomalies within each one. Our experiments with both synthetic and real-world data demonstrate the effectiveness and efficiency of the proposed solution. 1.
Adaptive Fastest Path Computation on a Road Network A Traffic Mining Approach.
Efficient fastest path computation in the presence of varying speed conditions on a large scale road network is an essential problem in modern navigation systems. Factors affecting road speed, such as weather, time of day, and vehicle type, need to be considered in order to select fast routes that match current driving conditions. Most existing systems compute fastest paths based on road Euclidean distance and a small set of predefined road speeds. However, “History is often the best teacher”. Historical traffic data or driving patterns are often more useful than the simple Euclidean distance-based computation because people must have good reasons to choose these routes, e.g., they may want to avoid those that pass through high crime areas at night or that likely encounter accidents, road construction, or traffic jams. In this paper, we present an adaptive fastest path algorithm capable of efficiently accounting for important driving and speed patterns mined from a large set of traffic data. The algorithm is based on the following observations: (1) The hierarchy of roads can be used to partition the road network into areas, and different path pre-computation strategies can be used at the area level, (2) we can limit our route search strategy to edges and path segments that are actually frequently traveled in the data, and (3) drivers usually traverse the road network through the largest roads available given the distance of the trip, except if there are small roads with a significant speed advantage over the large ones. Through an extensive experimental evaluation on real road networks we show that our algorithm provides desirable (short and well-supported) routes, and that it is significantly faster than competing methods.
Towards Graph Containment Search and Indexing.
Given a set of model graphs D and a query graph q, containment search aims to find all model graphs g ∈ D such that q contains g (q ⊇ g). Due to the wide adoption of graph models, fast containment search of graph data finds many applications in various domains. In comparison to traditional graph search that retrieves all the graphs containing q (q ⊆ g), containment search has its own indexing characteristics that have not yet been examined. In this paper, we perform a systematic study on these characteristics and propose a contrast subgraph-based indexing model, called cIndex. Contrast subgraphs capture the structure differences between model graphs and query graphs, and are thus perfect for indexing due to their high selectivity. Using a redundancy-aware feature selection process, cIndex can sort out a set of significant and distinctive contrast subgraphs and maximize its indexing capability. We show that it is NP-complete to choose the best set of indexing features, and our greedy algorithm can approximate the one-level optimal index within a ratio of 1 − 1/e. Taking this solution as a base indexing model, we further extend it to accommodate hierarchical indexing methodologies and apply data space clustering and sampling techniques to reduce the index construction time. The proposed methodology provides a general solution to containment search and indexing, not only for graphs, but also for any data with transitive relations as well. Experimental results on real test data show that cIndex achieves near-optimal pruning power on various containment search workloads, and confirms its obvious advantage over indices built for traditional graph search in this new scenario. 1.
TagSmart analysis and visualization for yeast mutant fitness data measured by tag microarrays.

On compressing frequent patterns.
A major challenge in frequent-pattern mining is the sheer size of its mining results. To compress the frequent patterns, we propose to cluster frequent patterns with a tightness measure δ (called δ-cluster), and select a representative pattern for each cluster. The problem of finding a minimum set of representative patterns is shown NP-Hard. We develop two greedy methods, RPglobal and RPlocal. The former has the guaranteed compression bound but higher computational complexity. The latter sacrifices the theoretical bounds but is far more efficient. Our performance study shows that the compression quality using RPlocal is very close to RPglobal, and both can reduce the number of closed frequent patterns by almost two orders of magnitude. Furthermore, RPlocal mines even faster than FPClose[10], a very fast closed frequent-pattern mining method. We also show that RPglobal and RPlocal can be combined together to balance the quality and efficiency.
Frequent pattern mining current status and future directions.

CrossClus user%2Dguided multi%2Drelational clustering.

Computing Iceberg Cubes by Top%2DDown and Bottom%2DUp Integration The StarCubing Approach.

Frequent Closed Sequence Mining without Candidate Maintenance.
 Previous studies have presented convincing arguments that a frequent pattern mining algorithm should not mine all frequent patterns but only the closed ones because the latter leads to not only a more compact yet complete result set but also better efficiency. However, most of the previously developed closed pattern mining algorithms work under the candidate maintenance-andtest paradigm, which is inherently costly in both runtime and space usage when the support threshold is low or the patterns become long. In this paper, we present BIDE, an efficient algorithm for mining frequent closed sequences without candidate maintenance. It adopts a novel sequence closure checking scheme called BI-Directional Extension and prunes the search space more deeply compared to the previous algorithms by using the BackScan pruning method. A thorough performance study with both sparse and dense, real, and synthetic data sets has demonstrated that BIDE significantly outperforms the previous algorithm: It consumes an order(s) of magnitude less memory and can be more than an order of magnitude faster. It is also linearly scalable in terms of database size.  
Constraint%2Dbased sequential pattern mining the pattern%2Dgrowth methods.
Constraints are essential for many sequential pattern mining applications. However, there is no systematic study on constraint-based sequential pattern mining. In this paper, we investigate this issue and point out that the framework developed for constrained frequent-pattern mining does not fit our mission well. An extended framework is developed based on a sequential pattern growth methodology. Our study shows that constraints can be effectively and efficiently pushed deep into the sequential pattern mining under this new framework. Moreover, this framework can
be extended to constraint-based structured pattern mining as well.
Introduction.
The use of monads to structure functional programs is described. Monads provide a convenient framework for simulating e ects found in other languages, such as global state, exception handling, output, or non-determinism. Three case studies are looked at in detail: how monads ease the modi cation of a simple evaluator; how monads act as the basis of a datatype of arrays subject to in-place update; and how monads can be used to build parsers.  
Semantic annotation of frequent patterns.
Using frequent patterns to analyze data has been one of the fundamental approaches in many data mining applications. Research in frequent pattern mining has so far mostly focused on developing efficient algorithms to discover various kinds of frequent patterns, but little attention has been paid to the important next step—interpreting the discovered frequent patterns. Although the compression and summarization of frequent patterns has been studied in some recent work, the proposed techniques there can only annotate a frequent pattern with nonsemantical information (e.g., support), which provides only limited help for a user to understand the patterns. In this article, we study the novel problem of generating semantic annotations for frequent patterns. The goal is to discover the hidden meanings of a frequent pattern by annotating it with in-depth, concise, and structured information. We propose a general approach to generate such an annotation for a frequent pattern by constructing its context model, selecting informative context indicators, and extracting representative transactions and semantically similar patterns. This general approach can well incorporate the user’s prior knowledge, and has potentially many applications, such as generating a dictionary-like description for a pattern, finding synonym patterns, discovering semantic relations, and summarizing semantic classes of a set of frequent patterns. Experiments
Warehousing and Mining Massive RFID Data Sets.

Mining compressed commodity workflows from massive RFID data sets.

Mining%2C Indexing%2C and Similarity Search in Graphs and Complex Structures.

On the Inverse Classification Problem and its Applications.
RESEARCH INTERESTS I am generally interested in data mining, data warehousing and database systems. My current research focuses on modeling, managing and analyzing large-scale graph and information network data.
Top%2DDown Mining of Interesting Patterns from Very High Dimensional Data.

C%2DCubing Efficient Computation of Closed Cubes by Aggregation%2DBased Checking.
It is well recognized that data cubing often produces huge outputs. Two popular efforts devoted to this problem are (1) iceberg cube, where only significant cells are kept, and (2) closed cube, where a group of cells which preserve roll-up/drill-down semantics are losslessly compressed to one cell. Due to its usability and importance, efficient computation of closed cubes still warrants a thorough study. In this paper, we propose a new measure, called closedness, for efficient closed data cubing. We show that closedness is an algebraic measure and can be computed efficiently and incrementally. Based on closedness measure, we develop an an aggregation-based approach, called C-Cubing (i.e., Closed-Cubing), and integrate it into two successful iceberg cubing algorithms: MM-Cubing and Star-Cubing. Our performance study shows that C-Cubing runs almost one order of magnitude faster than the previous approaches. We further study how the performance of the alternative algorithms of C-Cubing varies w.r.t the properties of the data sets. 1
Warehousing and Analyzing Massive RFID Data Sets.
Radio Frequency Identification (RFID) applications are set to play an essential role in object tracking and supply chain management systems. In the near future, it is expected that every major retailer will use RFID systems to track the movement of products from suppliers to warehouses, store backrooms and eventually to points of sale. The volume of information generated by such systems can be enormous as each individual item (a pallet, a case, or an SKU) will leave a trail of data as it moves through different locations. As a departure from the traditional data cube, we propose a new warehousing model that preserves object transitions while providing significant compression and path-dependent aggregates, based on the following observations: (1) items usually move together in large groups through early stages in the system (e.g., distribution centers) and only in later stages (e.g., stores) do they move in smaller groups, and (2) although RFID data is registered at the primitive level, data analysis usually takes place at a higher abstraction level. Techniques for summarizing and indexing data, and methods for processing a variety of queries based on this framework are developed in this study. Our experiments demonstrate the utility and feasibility of our design, data structure, and algorithms. 1
Searching Substructures with Superimposed Distance.
Efficient indexing techniques have been developed for the exact and approximate substructure search in large scale graph databases. Unfortunately, the retrieval problem of structures with categorical or geometric distance constraints is not solved yet. In this paper, we develop a method called PIS (Partition-based Graph Index and Search) to support similarity search on substructures with superimposed distance constraints. PIS selects discriminative fragments in a query graph and uses an index to prune the graphs that violate the distance constraints. We identify a criterion to distinguish the selectivity of fragments in multiple graphs and develop a partition method to obtain a set of highly selective fragments, which is able to improve the pruning performance. Experimental results show that PIS is effective in processing real graph queries. 1
How Bayesians Debug.

AC%2DClose Efficiently Mining Approximate Closed Itemsets by Core Pattern Recovery.
Recent studies have proposed methods to discover approximate frequent itemsets in the presence of random noise. By relaxing the rigid requirement of exact frequent pattern mining, some interesting patterns, which would previously be fragmented by exact pattern mining methods due to the random noise or measurement error, are successfully recovered. Unfortunately, a large number of “uninteresting ” candidates are explored as well during the mining process, as a result of the relaxed pattern mining methodology. This severely slows down the mining process. Even worse, it is hard for an end user to distinguish the recovered interesting patterns from these uninteresting ones. In this paper, we propose an efficient algorithm AC-Close to recover the approximate closed itemsets from “core patterns”. By focusing on the so-called core patterns, integrated with a top-down mining and several effective pruning strategies, the algorithm narrows down the search space to those potentially interesting ones. Experimental results show that AC-Close substantially outperforms the previously proposed method in terms of efficiency, while delivers a similar set of interesting recovered patterns. 1.
Motion%2DAlert Automatic Anomaly Detection in Massive Moving Objects.
Abstract. With recent advances in sensory and mobile computing technology, enormous amounts of data about moving objects are being collected. With such data, it becomes possible to automatically identify suspicious behavior in object movements. Anomaly detection in massive moving objects has many important applications, especially in surveillance, law enforcement, and homeland security. Due to the sheer volume of spatiotemporal and non-spatial data (such as weather and object type) associated with moving objects, it is challenging to develop a method that can efficiently and effectively detect anomalies of object movements in complex scenarios. The problem is further complicated by the fact that anomalies may occur at various levels of abstraction and be associated with different time and location granularities. In this paper, we analyze the problem of anomaly detection in moving objects and propose an efficient and scalable classification method, called motion-classifier, which proceeds in the following three steps. 1. Object movement features, called motifs, are extracted from the object paths. Each path consists of a sequence of motif expressions, associated with the values related to time and location. 2. To discover anomalies in object movements, motif-based generalization is performed that clusters similar object movement fragments and generalizes the movements based on the associated motifs. 3. With motif-based generalization, objects are put into a multi-level feature space and are classified by a classifier that can handle highdimensional feature spaces. We implemented the above method as one of the core components in our moving-object anomaly detection system, motion-alert. Our experiments show that the system is more accurate than traditional classification techniques. 1
Generating semantic annotations for frequent patterns with context analysis.
As a fundamental data mining task, frequent pattern mining has widespread applications in many different domains. Research in frequent pattern mining has so far mostly focused on developing efficient algorithms to discover various kinds of frequent patterns, but little attention has been paid to the important next step – interpreting the discovered frequent patterns. Although some recent work has studied the compression and summarization of frequent patterns, the proposed techniques can only annotate a frequent pattern with non-semantical information (e.g. support), which provides only limited help for a user to understand the patterns. In this paper, we propose the novel problem of generating semantic annotations for frequent patterns. The goal is to annotate a frequent pattern with in-depth, concise, and structured information that can better indicate the hidden meanings of the pattern. We propose a general approach to generate such an annotation for a frequent pattern by constructing its context model, selecting informative context indicators, and extracting representative transactions and semantically similar patterns. This general approach has potentially many applications such as generating a dictionarylike description for a pattern, finding synonym patterns, discovering semantic relations, and summarizing semantic classes of a set of frequent patterns. Experiments on different datasets show that our approach is effective in generating semantic pattern annotations.
Extracting redundancy%2Daware top%2Dk patterns.

Discovering interesting patterns through user%27s interactive feedback.

GPLAG detection of software plagiarism by program dependence graph analysis.
Along with the blossom of open source projects comes the convenience for software plagiarism. A company, if less self-disciplined, may be tempted to plagiarize some open source projects for its own products. Although current plagiarism detection tools appear sufficient for academic use, they are nevertheless short for fighting against serious plagiarists. For example, disguises like statement reordering and code insertion can effectively confuse these tools. In this paper, we develop a new plagiarism detection tool, called GPlag, which detects plagiarism by mining program dependence graphs (PDGs). A PDG is a graphic representation of the data and control dependencies within a procedure. Because PDGs are nearly invariant during plagiarism, GPlag is more effective than state-of-the-art tools for plagiarism detection. In order to make GPlag scalable to large programs, a statistical lossy filter is proposed to prune the plagiarism search space. Experiment study shows that GPlag is both effective and efficient: It detects plagiarism that easily slips over existing tools, and it usually takes a few seconds to find (simulated) plagiarism in programs having thousands of lines of code.
Ranking Outliers Using Symmetric Neighborhood Relationship.
Abstract. Mining outliers in database is to find exceptional objects that deviate from the rest of the data set. Besides classical outlier analysis algorithms, recent studies have focused on mining local outliers, i.e., the outliers that have density distribution significantly different from their neighborhood. The estimation of density distribution at the location of an object has so far been based on the density distribution of its k-nearest neighbors [2, 11]. However, when outliers are in the location where the density distributions in the neighborhood are significantly different, for example, in the case of objects from a sparse cluster close to a denser cluster, this may result in wrong estimation. To avoid this problem, here we propose a simple but effective measure on local outliers based on a symmetric neighborhood relationship. The proposed measure considers both neighbors and reverse neighbors of an object when estimating its density distribution. As a result, outliers so discovered are more meaningful. To compute such local outliers efficiently, several mining algorithms are developed that detects top-n outliers based on our definition. A comprehensive performance evaluation and analysis shows that our methods are not only efficient in the computation but also more effective in ranking outliers. 1
Mining Control Flow Abnormality for Logic Error Isolation.

Mining Interesting Patterns from Very High Dimensional Data A Top%2DDown Row Enumeration Approach.

Tensor space model for document analysis.
Vector Space Model (VSM) has been at the core of information retrieval for the past decades. VSM considers the documents as vectors in high dimensional space. In such a vector space, techniques like Latent Semantic Indexing (LSI), Support Vector Machines (SVM), Naive Bayes, etc., can be then applied for indexing and classification. However, in some cases, the dimensionality of the document space might be extremely large, which makes these techniques infeasible due to the curse of dimensionality. In this paper, we propose a novel Tensor Space Model for document analysis. We represent documents as the second order tensors, or matrices. Correspondingly, a novel indexing algorithm called Tensor Latent Semantic Indexing (TensorLSI) is developed in the tensor space. Our theoretical analysis shows that TensorLSI is much more computationally efficient than the conventional Latent Semantic Indexing, which makes it applicable for extremely large scale data set. Several experimental results on standard document data sets demonstrate the efficiency and effectiveness of our algorithm. Categories and Subject Descriptors:
Ranking objects based on relationships.
Text corpora are often enhanced by additional metadata which relate real-world entities, with each document in which such entities are discussed. Such relationships are typically obtained through widely available Information Extraction tools. At the same time, interesting known associations typically hold among these entities. For instance, a corpus might contain discussions on hotels, cities and airlines; fixed associations among these entities may include: airline A operates a flight to city C, hotel H is located in city C. A plethora of applications necessitate the identification of associated entities, each best matching a given set of keywords. Consider the sample query: Find a holiday package in a “pet-friendly ” hotel, located in a “historical ” yet “lively ” city, with travel operated by an “economical ” and “safe ” airline. These keywords are unlikely to occur in the textual description of entities themselves, (e.g., the actual hotel name or the city name or the airline name). Consequently to answer such queries, one needs to exploit both relationships between entities and documents (e.g., keyword “pet-friendly ” occurs in a document that contains an entity specifying a hotel name H), and the known associations between entities (e.g., hotel H is located in city C). In this work, we focus on the class of “entity package finder” queries outlined above. We demonstrate that existing techniques cannot be efficiently adapted to solve this problem, as the resulting algorithm relies on estimations with excessive runtime and/or storage overheads. We propose an efficient algorithm to process such queries, over large corpora. We devise early pruning and termination strategies, in the presence of joins and aggregations (executed on entities extracted from text), that do not depend on any estimates. Our analysis and experimental evaluation on real and synthetic data demonstrates the efficiency and scalability of our approach. 1.
Failure proximity a fault localization%2Dbased approach.
Recent software systems usually feature an automated failure reporting system, with which a huge number of failing traces are collected every day. In order to prioritize fault diagnosis, failing traces due to the same fault are expected to be grouped together. Previous methods, by hypothesizing that similar failing traces imply the same fault, cluster failing traces based on the literal trace similarity, which we call trace proximity. However, since a fault can be triggered in many ways, failing traces due to the same fault can be quite different. Therefore, previous methods actually group together traces exhibiting similar behaviors, like similar branch coverage, rather than traces due to the same fault. In this paper, we propose a new type of failure proximity, called R-Proximity, which regards two failing traces as similar if they suggest roughly the same fault location. The fault location each failing case suggests is automatically obtained with Sober, an existing statistical debugging tool. We show that with R-Proximity, failing traces due to the same fault can be grouped together. In addition, we find that R-Proximity is helpful for statistical debugging: It can help developers interpret and utilize the statistical debugging result. We illustrate the usage of R-Proximity with a case study on the grep program and some experiments on the Siemens suite, and the result clearly demonstrates the advantage of R-Proximity over trace proximity.
Towards Robust Indexing for Ranked Queries.
RESEARCH INTERESTS I am generally interested in data mining, data warehousing and database systems. My current research focuses on modeling, managing and analyzing large-scale graph and information network data.
LinkClus Efficient Clustering via Heterogeneous Semantic Links.
Data objects in a relational database are cross-linked with each other via multi-typed links. Links contain rich semantic information that may indicate important relationships among objects. Most current clustering methods rely only on the properties that belong to the objects per se. However, the similarities between objects are often indicated by the links, and desirable clusters cannot be generated using only the properties of objects. In this paper we explore linkage-based clustering, in which the similarity between two objects is measured based on the similarities between the objects linked with them. In comparison with a previous study (SimRank) that computes links recursively on all pairs of objects, we take advantage of the power law distribution of links, and develop a hierarchical structure called SimTree to represent similarities in multi-granularity manner. This method avoids the high cost of computing and storing pairwise similarities but still thoroughly explore relationships among objects. An efficient algorithm is proposed to compute similarities between objects by avoiding pairwise similarity computations through merging computations that go through the same branches in the SimTree. Experiments show the proposed approach achieves high efficiency, scalability, and accuracy in clustering multi-typed linked objects. 1.
Answering Top%2Dk Queries with Multi%2DDimensional Selections The Ranking Cube Approach.
Observed in many real applications, a top-k query often consists of two components to reflect a user’s preference: a selection condition and a ranking function. A user may not only propose ad hoc ranking functions, but also use different interesting subsets of the data. In many cases, a user may want to have a thorough study of the data by initiating a multi-dimensional analysis of the top-k query results. Previous work on top-k query processing mainly focuses on optimizing data access according to the ranking function only. The problem of efficient answering top-k queries with multidimensional selections has not been well addressed yet. This paper proposes a new computational model, called ranking cube, for efficient answering top-k queries with multidimensional selections. We define a rank-aware measure for the cube, capturing our goal of responding to multidimensional ranking analysis. Based on the ranking cube, an efficient query algorithm is developed which progressively retrieves data blocks until the top-k results are found. The curse of dimensionality is a well-known challenge for the data cube and we cope with this difficulty by introducing a new technique of ranking fragments. Our experiments on Microsoft’s SQL Server 2005 show that our proposed approaches have significant improvement over the previous methods. 1.
FlowCube Constructuing RFID FlowCubes for Multi%2DDimensional Analysis of Commodity Flows.

Error%2DAdaptive and Time%2DAware Maintenance of Frequency Counts over Data Streams.
Abstract. Maintaining frequency counts for items over data stream has a wide range of applications such as web advertisement fraud detection. Study of this problem has attracted great attention from both researchers and practitioners. Many algorithms have been proposed. In this paper, we propose a new method, error-adaptive pruning method, to maintain frequency more accurately. We also propose a method called fractionization to record time information together with the frequency information. Using these two methods, we design three algorithms for finding frequent items and top-k frequent items. Experimental results show these methods are effective in terms of improving the maintenance accuracy. 1
Feature%2Dbased similarity search in graph structures.
Similarity search of complex structures is an important operation in graph-related applications since exact matching is often too restrictive. In this article, we investigate the issues of substructure similarity search using indexed features in graph databases. By transforming the edge relaxation ratio of a query graph into the maximum allowed feature misses, our structural filtering algorithm can filter graphs without performing pairwise similarity computation. It is further shown that using either too few or too many features can result in poor filtering performance. Thus the challenge is to design an effective feature set selection strategy that could maximize the filtering capability. We prove that the complexity of optimal feature set selection is Ω(2 m) in the worst case, where m is the number of features for selection. In practice, we identify several criteria to build effective feature sets for filtering, and demonstrate that combining features with similar size and selectivity can improve the filtering and search performance significantly within a multi-filter composition framework. The proposed feature-based filtering concept can be generalized and applied to searching approximate non-consecutive sequences, trees, and other structured data as well. Categories and Subject Descriptors: H.2.4 [Database Management]: Systems – Query process-This is a preliminary release of an article accepted by ACM Transactions on Database Systems. The definitive version is currently in production at ACM and, when released, will supersede this version.
Integrative Array Analyzer a software package for analysis of cross%2Dplatform and cross%2Dspecies microarray data.

An Erratum on %22Pushing Convertible Constraints in Frequent Itemset Mining%22.
Recent work has highlighted the importance of the constraint-based mining paradigm in the context of frequent itemsets, associations, correlations, sequential patterns, and many other interesting patterns in large databases. In this paper, we study constraints which cannot be handled with existing theory and techniques. For example,  	 604 -  ,   2520   ,     190  (  can contain items of arbitrary values)   &#034;!$# %&#039;&amp;)(  , are customarily regarded as &#034;tough&#034; constraints in that they cannot be pushed inside an algorithm such as Apriori. We develop a notion of convertible constraints and systematically analyze, classify, and characterize this class. We also develop techniques which enable them to be readily pushed deep inside the recently developed FP-growth algorithm for frequent itemset mining. Results from our detailed experiments show the effectiveness of the techniques developed. 1. Introduction  It has been well recognized that frequent pattern minin...
Regression Cubes with Lossless Compression and Aggregation.
Abstract—As OLAP engines are widely used to support multidimensional data analysis, it is desirable to support in data cubes advanced statistical measures, such as regression and filtering, in addition to the traditional simple measures such as count and average. Such new measures will allow users to model, smooth, and predict the trends and patterns of data. Existing algorithms for simple distributive and algebraic measures are inadequate for efficient computation of statistical measures in a multidimensional space. In this paper, we propose a fundamentally new class of measures, compressible measures, in order to support efficient computation of the statistical models. For compressible measures, we compress each cell into an auxiliary matrix with a size independent of the number of tuples. We can then compute the statistical measures for any data cell from the compressed data of the lower-level cells without accessing the raw data. Time- and space-efficient lossless aggregation formulae are derived for regression and filtering measures. Our analytical and experimental studies show that the resulting system, regression cube, substantially reduces the memory usage and the overall response time for statistical analysis of multidimensional data. Index Terms—Aggregation, compression, data cubes, OLAP. 1
A Framework for On%2DDemand Classification of Evolving Data Streams.

Closed Constrained Gradient Mining in Retail Databases.

Efficient Classification across Multiple Database Relations A CrossMine Approach.

Statistical Debugging A Hypothesis Testing%2DBased Approach.
Abstract—Manual debugging is tedious, as well as costly. The high cost has motivated the development of fault localization techniques, which help developers search for fault locations. In this paper, we propose a new statistical method, called SOBER, which automatically localizes software faults without any prior knowledge of the program semantics. Unlike existing statistical approaches that select predicates correlated with program failures, SOBER models the predicate evaluation in both correct and incorrect executions and regards a predicate as fault-relevant if its evaluation pattern in incorrect executions significantly diverges from that in correct ones. Featuring a rationale similar to that of hypothesis testing, SOBER quantifies the fault relevance of each predicate in a principled way. We systematically evaluate SOBER under the same setting as previous studies. The result clearly demonstrates the effectiveness: SOBER could help developers locate 68 out of the 130 faults in the Siemens suite by examining no more than 10 percent of the code, whereas the Cause Transition approach proposed by Holger et al. [6] and the statistical approach by Liblit et al. [12] locate 34 and 52 faults, respectively. Moreover, the effectiveness of SOBER is also evaluated in an “imperfect world, ” where the test suite is either inadequate or only partially labeled. The experiments indicate that SOBER could achieve competitive quality under these harsh circumstances. Two case studies with grep 2.2 and bc 1.06 are reported, which shed light on the applicability of SOBER on reasonably large programs. Index Terms—Debugging aids, statistical methods, statistical debugging. 1
Orthogonal Laplacianfaces for Face Recognition.
[30] V. Patrascu and V. Buzuloiu, “Image dynamic range enhancement in
Image clustering with tensor representation.

SOBER statistical model%2Dbased bug localization.

Mining closed relational graphs with connectivity constraints.

Mining Closed Relational Graphs with Connectivity Constraints.

Mining Evolving Customer%2DProduct Relationships in Multi%2DDimensional Space.
Previous work on mining transactional database has focused primarily on mining frequent itemsets, association rules, and sequential patterns. However, interesting relationships between customers and items, especially their evolution with time, have not been studied thoroughly. In this paper, we propose a Gaussin transformation-based regression model that captures time-variant relationships between customers and products. Moreover, since it is interesting to discover such relationships in a multi-dimensional space, an efficient method has been developed to compute multi-dimensional aggregates of such curves in a data cube environment. Our experimental results have demonstrated the promise of the approach.
Mining coherent dense subgraphs across massive biological networks for functional discovery.

Summarizing itemset patterns a profile%2Dbased approach.
Frequent-pattern mining has been studied extensively on scalable methods for mining various kinds of patterns including itemsets, sequences, and graphs. However, the bottleneck of frequent-pattern mining is not at the efficiency but at the interpretability, due to the huge number of patterns generated by the mining process. In this paper, we examine how to summarize a collection of itemset patterns using only K representatives, a small number of patterns that a user can handle easily. The K representatives should not only cover most of the frequent patterns but also approximate their supports. A generative model is built to extract and profile these representatives, under which the supports of the patterns can be easily recovered without consulting the original dataset. Based on the restoration error, we propose a quality measure function to determine the optimal value of parameter K. Polynomial time algorithms are developed together with several optimization heuristics for efficiency improvement. Empirical studies indicate that we can obtain compact summarization in real datasets.
Mining closed relational graphs with connectivity constraints.

Cross%2Drelational clustering with user%27s guidance.

Parallel mining of closed sequential patterns.
Discovery of sequential patterns is an essential data mining task with broad applications. Among several variations of sequential patterns, closed sequential pattern is the most useful one since it retains all the information of the complete pattern set but is often much more compact than it. Unfortunately, there is no parallel closed sequential pattern mining method proposed yet. In this paper we develop an algorithm, called Par-CSP (Parallel Closed Sequential Pattern mining), to conduct parallel mining of closed sequential patterns on a distributed memory system. Par-CSP partitions the work among the processors by exploiting the divide-and-conquer property so that the overhead of interprocessor communication is minimized. Par-CSP applies dynamic scheduling to avoid processor idling. Moreover, it employs a technique, called selective sampling, to address the load imbalance problem. We implement Par-CSP using MPI on a 64-node Linux cluster. Our experimental results show that Par-CSP attains good parallelization efficiencies on various input datasets.
Efficient Classification from Multiple Heterogeneous Databases.
With the fast expansion of computer networks, it is inevitable to study data mining on heterogeneous databases. In this paper we propose MDBM, an accurate and efficient approach for classification on multiple heterogeneous databases. We propose a regression-based method for predicting the usefulness of inter-database links that serve as bridges for information transfer, because such links are automatically detected and may or may not be useful or even valid. Because of the high cost of inter-database communication, MDBM employs a new strategy for cross-database classification, which finds and performs actions with high benefit-to-cost ratios. The experiments show that MDBM achieves high accuracy in cross-database classification, with much higher efficiency than previous approaches.
Community Mining from Multi%2Drelational Networks.
Abstract. Social network analysis has attracted much attention in recent years. Community mining is one of the major directions in social network analysis. Most of the existing methods on community mining assume that there is only one kind of relation in the network, and moreover, the mining results are independent of the users ’ needs or preferences. However, in reality, there exist multiple, heterogeneous social networks, each representing a particular kind of relationship, and each kind of relationship may play a distinct role in a particular task. In this paper, we systematically analyze the problem of mining hidden communities on heterogeneous social networks. Based on the observation that different relations have different importance with respect to a certain query, we propose a new method for learning an optimal linear combination of these relations which can best meet the user’s expectation. With the obtained relation, better performance can be achieved for community mining. 1
Efficient Processing of Ranked Queries with Sweeping Selection.
Abstract. Existing methods for top-k ranked query employ techniques including sorting, updating thresholds and materializing views. In this paper, we propose two novel index-based techniques for top-k ranked query: (1) indexing the layered skyline, and (2) indexing microclusters of objects into a grid structure. We also develop efficient algorithms for ranked query by locating the answer points during the sweeping of the line/hyperplane of the score function over the indexed objects. Both methods can be easily plugged into typical multi-dimensional database indexes. The comprehensive experiments not only demonstrate that our methods outperform the existing ones, but also illustrate that the application of data mining technique (microclustering) is a useful and effective solution for database query processing. 1
A sampling%2Dbased framework for parallel data mining.
The goal of data mining algorithm is to discover useful information embedded in large databases. Frequent itemset mining and sequential pattern mining are two important data mining problems with broad applications. Perhaps the most efficient way to solve these problems sequentially is to apply a pattern-growth algorithm, which is a divide-and-conquer algorithm [9, 10]. In this paper, we present a framework for parallel mining frequent itemsets and sequential patterns based on the divide-and-conquer strategy of pattern growth. Then, we discuss the load balancing problem and introduce a sampling technique, called selective sampling, to address this problem. We implemented parallel versions of both frequent itemsets and sequential pattern mining algorithms following our framework. The experimental results show that our parallel algorithms usually achieve excellent speedups. Categories and Subject Descriptors D.1 [Programming Techniques]: Concurrent programming—parallel programming; H.2.8 [Database Management]:
Mining Behavior Graphs for %22Backtrace%22 of Noncrashing Bugs.
Analyzing the executions of a buggy software program is essentially a data mining process. Although many interesting methods have been developed to trace crashing bugs (such as memory violation and core dumps), it is still difficult to analyze noncrashing bugs (such as logical errors). In this paper, we develop a novel method to classify the structured traces of program executions using software behavior graphs. By analyzing the correct and incorrect executions, we have made good progress at the isolation of program regions that may lead to the faulty executions. The classification framework is built on an integration of closed graph mining and SVM classification. More interestingly, suspicious regions are identified through the capture of the classification accuracy change, which is measured incrementally during program execution. Our performance study and case-based experiments show that our approach is both effective and efficient.
SeqIndex Indexing Sequences by Sequential Pattern Analysis.
In this paper, we study the issues related to the design and construction of high-performance sequence index structures in large sequence databases. To build effective indices, a novel method, called SeqIndex, is proposed, in which the selection of indices is based on the analysis of discriminative, frequent sequential patterns mined from large sequence databases. Such an analysis leads to the construction of compact and effective indexing structures. Furthermore, we eliminate the requirement of setting an optimal support threshold beforehand, which is difficult for users to provide in practice. The discriminative, frequent pattern based indexing method is proven very effective based on our performance study. 1
Substructure Similarity Search in Graph Databases.
Advanced database systems face a great challenge raised by the emergence of massive, complex structural data in bioinformatics, chem-informatics, and many other applications. The most fundamental support needed in these applications is the efficient search of complex structured data. Since exact matching is often too restrictive, similarity search of complex structures becomes a vital operation that must be supported efficiently. In this paper, we investigate the issues of substructure similarity search using indexed features in graph databases. By transforming the edge relaxation ratio of a query graph into the maximum allowed missing features, our structural filtering algorithm, called Grafil, can filter many graphs without performing pairwise similarity computations. It is further shown that using either too few or too many features can result in poor filtering performance. Thus the challenge is to design an effective feature set selection strategy for filtering. By examining the effect of different feature selection mechanisms, we develop a multi-filter composition strategy, where each filter uses a distinct and complementary subset of the features. We identify the criteria to form effective feature sets for filtering, and demonstrate that combining features with similar size and selectivity can improve the filtering and search performance significantly. Moreover, the concept presented in Grafil can be applied to searching approximate non-consecutive sequences, trees, and other complicated structures as well. 1.
GraphMiner a structural pattern%2Dmining system for large disk%2Dbased graph databases and its applications.

Searching for Related Objects in Relational Databases.
To discover knowledge or retrieve information from a relational database, a user often needs to find objects related to certain source objects. There are two main challenges in building an e#ective object search system: the huge amount of objects in the database and the large number of di#erent relationships between objects. In this paper we introduce Ross, an e#cient and accurate relational object search system. Ross accepts complex queries that enable users to specify the relationships among objects. To measure the relationships of join paths, Ross considers the di#erent semantics of di#erent joins, and combines both selectivity and lengths of join paths to measure their strengths. A novel approach is used to find the best join paths between relations, which converts the database schema into a graph, so that the shortest paths in the graph correspond to best join paths in the database. Ross uses a stream-based system architecture to handle complex queries containing logical operators, which can find the most related objects upon users&#039; requests. Comprehensive experiments are conducted to show the high scalability and e#ectiveness of Ross.
Mining Compressed Frequent%2DPattern Sets.
A major challenge in frequent-pattern mining is the sheer size of its mining results. In many cases, a high min sup threshold may discover only commonsense patterns but a low one may generate an explosive number of output patterns, which severely restricts its usage. In this paper, we study the problem of compressing frequent-pattern sets. Typically, frequent patterns can be clustered with a tightness measure δ (called δ-cluster), and a representative pattern can be selected for each cluster. Unfortunately, finding a minimum set of representative patterns is NP-Hard. We develop two greedy methods, RPglobal and RPlocal. The former has the guaranteed compression bound but higher computational complexity. The latter sacrifices the theoretical bounds but is far more efficient. Our performance study shows that the compression quality using RPlocal is very close to RPglobal, and both can reduce the number of closed frequent patterns by almost two orders of magnitude. Furthermore, RPlocal mines even faster than FPClose[11], a very fast closed frequentpattern mining method. We also show that RPglobal and RPlocal can be combined together to balance the quality and efficiency. 1
Survey of Biodata Analysis from a Data Mining Perspective.

Mining Data Streams.
Abstract: Mining data streams has raised a number of research challenges for the data mining community. These challenges include the limitations of computational resources, especially because mining streams of data most likely be done on a mobile device with limited resources. Also due to the continuality of data streams, the algorithm should have only one pass or less over the incoming data records. In this article, our Algorithm Output Granularity (AOG) approach in mining data streams is discussed. AOG is a novel adaptable approach that can cope with the challenging inherent features of data streams. We also show the results for AOG based clustering in a resource constrained environment.
Graph indexing based on discriminative frequent structure analysis.

On High Dimensional Projected Clustering of Data Streams.

Making SVMs Scalable to Large Data Sets using Hierarchical Cluster Indexing.
Support vector machines (SVMs) have been promising methods for classification and regression analysis due to their solid mathematical foundations, which include two desirable properties: margin maximization and non-linear classification using kernels. However, despite these prominent properties, SVMs are usually not chosen for large-scale data mining problems because their training complexity is highly dependent on the data set size. Unlike traditional pattern recognition and machine learning, real-world data mining applications often involve huge num-bers of data records. Thus it is too expensive to perform multiple scans on the entire data set, and it is also infeasible to put the data set in memory. This paper presents a method, Clustering-Based SVM (CB-SVM), that maximizes the SVM performance for very large data sets given a limited amount of resource, e.g., memory. CB-SVM applies a hierarchical micro-clustering algorithm that scans the entire data set only once to provide an SVM with high quality samples. These samples carry statistical summaries of the data and maximize the benefit of learning. Our analyses show that the training complexity of CB-SVM is quadratically dependent on the number of support vectors, which is usually much less than that of the entire data set. Our experiments on synthetic and real-world data sets show that CB-SVM is highly scalable for very large data sets and very accurate in terms of classification. I.
Stream Cube An Architecture for Multi%2DDimensional Analysis of Data Streams.

Document Clustering Using Locality Preserving Indexing.
Abstract—We propose a novel document clustering method which aims to cluster the documents into different semantic classes. The document space is generally of high dimensionality and clustering in such a high dimensional space is often infeasible due to the curse of dimensionality. By using Locality Preserving Indexing (LPI), the documents can be projected into a lower-dimensional semantic space in which the documents related to the same semantics are close to each other. Different from previous document clustering methods based on Latent Semantic Indexing (LSI) or Nonnegative Matrix Factorization (NMF), our method tries to discover both the geometric and discriminating structures of the document space. Theoretical analysis of our method shows that LPI is an unsupervised approximation of the supervised Linear Discriminant Analysis (LDA) method, which gives the intuitive motivation of our method. Extensive experimental evaluations are performed on the Reuters-21578 and TDT2 data sets. Index Terms—Document clustering, locality preserving indexing, dimensionality reduction, semantics. æ 1
Divide%2Dand%2DApproximate A Novel Constraint Push Strategy for Iceberg Cube Mining.

TFP An Efficient Algorithm for Mining Top%2DK Frequent Closed Itemsets.
Abstract—Frequent itemset mining has been studied extensively in literature. Most previous studies require the specification of a min_support threshold and aim at mining a complete set of frequent itemsets satisfying min_support. However, in practice, it is difficult for users to provide an appropriate min_support threshold. In addition, a complete set of frequent itemsets is much less compact than a set of frequent closed itemsets. In this paper, we propose an alternative mining task: mining top-k frequent closed itemsets of length no less than min_l, where k is the desired number of frequent closed itemsets to be mined, and min_l is the minimal length of each itemset. An efficient algorithm, called TFP, is developed for mining such itemsets without mins_support. Starting at min_support = 0 and by making use of the length constraint and the properties of top-k frequent closed itemsets, min_support can be raised effectively and FP-Tree can be pruned dynamically both during and after the construction of the tree using our two proposed methods: the closed node count and descendant_sum. Moreover, mining is further speeded up by employing a top-down and bottom-up combined FP-Tree traversing strategy, a set of search space pruning methods, a fast 2-level hash-indexed result tree, and a novel closed itemset verification scheme. Our extensive performance study shows that TFP has high performance and linear scalability in terms of the database size. Index Terms—Data mining, frequent itemset, association rules, mining methods and algorithms. 1
TSP Mining top%2Dk closed sequential patterns.
Sequential pattern mining has been studied extensively in data mining community. Most previous studies require the specification of a minimum support threshold to perform the mining. However, it is difficult for users to provide an appropriate threshold in practice. To overcome this difficulty, we propose an alternative task: mining top-k frequent closed sequential patterns of length no less than ##### , where # is the desired number of closed sequential patterns to be mined, and##### # is the minimum length of each pattern. We mine closed patterns since they are compact representations of frequent patterns.
A tribute to Professor Hongjun Lu.

CrossMine Efficient Classification Across Multiple Database Relations.
Most of today&#039;s structured data is stored in relational databases. Such a database consists of multiple relations which are linked together conceptually via entity-relationship links in the design of relational database schemas. Multi-relational classification can be widely used in many disciplines, such as financial decision making, medical research, and geographical applications. However, most classification approaches only work on single &#034;flat&#034; data relations. It is usually difficult to convert multiple relations into a single flat relation without either introducing huge, undesirable &#034;universal relation&#034; or losing essential information. Previous works using Inductive Logic Programming approaches (recently also known as Relational Mining) have proven effective with high accuracy in multi-relational classification. Unfortunately, they suffer from poor scalability w.r.t. the number of relations and the number of attributes in databases.
Mining complex matchings across Web query interfaces.

CrossMine Efficient Classification Across Multiple Database Relations.
Most of today&#039;s structured data is stored in relational databases. Such a database consists of multiple relations which are linked together conceptually via entity-relationship links in the design of relational database schemas. Multi-relational classification can be widely used in many disciplines, such as financial decision making, medical research, and geographical applications. However, most classification approaches only work on single &#034;flat&#034; data relations. It is usually difficult to convert multiple relations into a single flat relation without either introducing huge, undesirable &#034;universal relation&#034; or losing essential information. Previous works using Inductive Logic Programming approaches (recently also known as Relational Mining) have proven effective with high accuracy in multi-relational classification. Unfortunately, they suffer from poor scalability w.r.t. the number of relations and the number of attributes in databases.
BIDE Efficient Mining of Frequent Closed Sequences.
Previous studies have presented convincing arguments that a frequent pattern mining algorithm should not mine all frequent patterns but only the closed ones because the latter leads to not only more compact yet complete result set but also better efficiency. However, most of the previously developed closed pattern mining algorithms work under the candidate maintenance-and-test paradigm which is inherently costly in both runtime and space usage when the support threshold is low or the patterns become long.
Scalable Construction of Topic Directory with Nonparametric Closed Termset Mining.

Discovering complex matchings across web query interfaces a correlation mining approach.
To enable information integration, schema matching is a critical step for discovering semantic correspondences of attributes across heterogeneous sources. While complex matchings are common, because of their far more complex search space, most existing techniques focus on simple 1:1 matchings. To tackle this challenge, this paper takes a conceptually novel approach by viewing schema matching as correlation mining, for our task of matching Web query interfaces to integrate the myriad databases on the Internet. On this &#034;deep Web,&#034; query interfaces generally form complex matchings  between attribute groups (e.g.,    corresponds to    name, last name} in the Books domain). We observe that the cooccurrences patterns across query interfaces often reveal such complex semantic relationships: grouping attributes (e.g.,    last name}) tend to be co-present in query interfaces and thus positively correlated. In contrast, synonym attributes are negatively correlated because they rarely co-occur. This insight enables us to discover complex matchings by a correlation mining approach. In particular, we develop the DCM framework, which consists of data preparation, dual mining of positive and negative correlations, and finally matching selection. Unlike previous correlation mining algorithms, which mainly focus on finding strong positive correlations, our algorithm cares both positive and negative correlations, especially the subtlety of negative correlations, due to its special importance in schema matching. This leads to the introduction of a new correlation measure, H-measure, distinct from those proposed in previous work. We evaluate our approach extensively and the results show good accuracy for discovering complex matchings.
On demand classification of data streams.
Current models of the classification problem do not e#ectively handle bursts of particular classes coming in at different times. In fact, the current model of the classification problem simply concentrates on methods for one-pass classification modeling of very large data sets. Our model for data stream classification views the data stream classification problem from the point of view of a dynamic approach in which simultaneous training and testing streams are used for dynamic classification of data sets. This model reflects real life situations e#ectively, since it is desirable to classify test streams in real time over an evolving training and test stream. The aim here is to create a classification system in which the training model can adapt quickly to the changes of the underlying data stream. In order to achieve this goal, we propose an on-demand classification process which can dynamically select the appropriate window of past training data to build the classifier. The empirical results indicate that the system maintains a high classification accuracy in an evolving data stream, while providing an e#cient solution to the classification task.
IncSpan incremental mining of sequential patterns in large database.
Many real life sequence databases grow incrementally. It is undesirable to mine sequential patterns from scratch each time when a small set of sequences grow, or when some new sequences are added into the database. Incremental algorithm should be developed for sequential pattern mining so that mining can be adapted to incremental database updates. However, it is nontrivial to mine sequential patterns incrementally, especially when the existing sequences grow incrementally because such growth may lead to the generation of many new patterns due to the interactions of the growing subsequences with the original ones. In this study, we develop an efficient algorithm, IncSpan, for incremental mining of sequential patterns, by exploring some interesting properties. Our performance study shows that IncSpan outperforms some previously proposed incremental algorithms as well as a non-incremental one with a wide margin.
Clustering moving objects.

Mining scale%2Dfree networks using geodesic clustering.
Many real-world graphs have been shown to be scale-free--- vertex degrees follow power law distributions, vertices tend to cluster, and the average length of all shortest paths is small. We present a new model for understanding scale-free networks based on multilevel geodesic approximation, using a new data structure called a multilevel mesh. Using this
CCMine Efficient Mining of Confidence%2DClosed Correlated Patterns.
Correlated pattern mining has become increasingly important recently as an alternative or an augmentation of association rule mining. Though correlated pattern mining...
Mining Thick Skylines over Large Databases.
Abstract. People recently are interested in a new operator, called skyline [3], which returns the objects that are not dominated by any other objects with regard to certain measures in a multi-dimensional space. Recent work on the skyline operator [3, 15, 8, 13, 2] focuses on efficient computation of skylines in large databases. However, such work gives users only thin skylines, i.e., single objects, which may not be desirable in some real applications. In this paper, we propose a novel concept, called thick skyline, which recommends not only skyline objects but also their nearby neighbors within ε-distance. Efficient computation methods are developed including (1) two efficient algorithms, Sampling-and-Pruning and Indexing-and-Estimating, to find such thick skyline with the help of statistics or indexes in large databases, and (2) a highly efficient Microcluster-based algorithm for mining thick skyline. The Microclusterbased method not only leads to substantial savings in computation but also provides a concise representation of the thick skyline in the case of high cardinalities. Our experimental performance study shows that the proposed methods are both efficient and effective. 1
Graph Indexing A Frequent Structure%2Dbased Approach.
Graph has become increasingly important in modelling complicated structures and schemaless data such as proteins, chemical compounds, and XML documents. Given a graph query, it is desirable to retrieve graphs quickly from a large database via graph-based indices. In this paper, we investigate the issues of indexing graphs and propose a novel solution by applying a graph mining technique. Di#erent from the existing path-based methods, our approach, called gIndex, makes use of frequent substructure as the basic indexing feature. Frequent substructures are ideal candidates since they explore the intrinsic characteristics of the data and are relatively stable to database updates. To reduce the size of index structure, two techniques, size-increasing support constraint  and discriminative fragments, are introduced. Our performance study shows that gIndex has 10 times smaller index size, but achieves 3-10 times better performance in comparison with a typical path-based method, GraphGrep. The gIndex approach not only provides an elegant solution to the graph indexing problem, but also demonstrates how database indexing and query processing can benefit from data mining, especially frequent pattern mining. Furthermore, the concepts developed here can be applied to indexing sequences, trees, and other complicated structures as well.
MAIDS Mining Alarming Incidents from Data Streams.
Real-time surveillance systems, network and telecommunication systems, and other dynamic processes often generate tremendous (potentially infinite) volume of stream data. Effective analysis of such stream data poses great challenges to database and data mining researchers, due to its unique features, such as single-scan algorithm, multi-dimensional online analysis, fast response time, etc.
Continuous K%2DNearest Neighbor Search for Moving Objects.
The paper describes a new method of continuously monitoring the    nearest neighbors of a given object in the mobile environment. Instead of monitoring all    nearest neighbors, we choose to monitor the    -th (nearest) neighbor since the necessary condition of changes in the KNN is the change   -th neighbor. In addition, rather than in the original space, we consider the moving objects in a transformed time-distance (TD) space, where each object is represented by a curve. A beach-line algorithm is developed to monitor the change of the    -th neighbor, which enables us to maintain the KNN incrementally. An extensive empirical study shows that the beach-line algorithm outperforms the most efficient existing algorithm by a wide margin, especially when    or    (the total number of objects) is large.
MM%2DCubing Computing Iceberg Cubes by Factorizing the Lattice Space.
The data cube and iceberg cube computation problem has been studied by many researchers. There are three major approaches developed in this direction: (1) top-down computation, represented by MultiWay array aggregation [22], which utilizes shared computation and performs well on dense data sets; (2) bottom-up computation, represented by BUC [6], which takes advantage of Apriori Pruning and performs well on sparse data sets; and (3) integrated top-down and bottom-up computation, represented by StarCubing [21], which takes advantages of both and has high performance in most cases. However, the performance of Star-Cubing degrades in very sparse data sets due to the additional cost introduced by the tree structure. None of the three approaches achieves uniformly high performance on all kinds of data sets.
High%2DDimensional OLAP A Minimal Cubing Approach.
Data cube has been playing an essential role  in fast OLAP (online analytical processing)  in many multi-dimensional data warehouses.
A Framework for Projected Clustering of High Dimensional Data Streams.
The data stream problem has been studied extensively  in recent years, because of the great  ease in collection of stream data. The nature  of stream data makes it essential to use  algorithms which require only one pass over  the data. Recently, single-scan, stream analysis  methods have been proposed in this context. However,
Mining Frequent Patterns without Candidate Generation A Frequent%2DPattern Tree Approach.
Mining frequent patterns in transaction databases, time-series databases, and many other kinds of databases has been studied popularly in data mining research. Most of the previous studies adopt an Apriori-like candidate set generation-and-test approach. However, candidate set generation is still costly, especially when there exist a large number of patterns and/or long patterns. In this study,  we propose a novel
frequent-pattern tree
(FP-tree) structure, which is an extended prefix-tree
structure for storing compressed, crucial information about frequent patterns, and develop an efficient FP-tree-
based mining method, FP-growth, for mining the complete set of frequent patterns by pattern fragment growth.
Efficiency of mining is achieved with three techniques: (1) a large database is compressed into a condensed,
smaller data structure, FP-tree which avoids costly, repeated database scans, (2) our FP-tree-based mining adopts
a pattern-fragment growth method to avoid the costly generation of a large number of candidate sets, and (3) a
partitioning-based, divide-and-conquer method is used to decompose the mining task into a set of smaller tasks for
mining confined patterns in conditional databases, which dramatically reduces the search space. Our performance
study shows that the FP-growth method is efficient and scalable for mining both long and short frequent patterns,
and is about an order of magnitude faster than the Apriori algorithm and also faster than some recently reported
new frequent-pattern mining methods
Pushing Convertible Constraints in Frequent Itemset Mining.

PEBL Web Page Classification without Negative Examples.
Web page classification is one of the essential techniques for Web mining because classifying Web pages of an interesting  class is often the first step of mining the Web. However, constructing a classifier for an interesting class requires laborious preprocessing  such as collecting positive and negative training examples. For instance, in order to construct a &#034;homepage&#034; classifier, one  needs to collect a sample of homepages (positive examples) and a sample of nonhomepages (negative examples). In particular,  collecting negative training examples requires arduous work and caution to avoid bias. This paper presents a framework, called  Positive Example Based Learning (PEBL), for Web page classification which eliminates the need for manually collecting negative  training examples in preprocessing. The PEBL framework applies an algorithm, called Mapping-Convergence (M-C), to achieve high  classification accuracy (with positive and unlabeled data) as high as that of a traditional SVM (with positive and negative data). M-C  runs in two stages: the mapping stage and convergence stage. In the mapping stage, the algorithm uses a weak classifier that draws  an initial approximation of &#034;strong&#034; negative data. Based on the initial approximation, the convergence stage iteratively runs an internal  classifier (e.g., SVM) which maximizes margins to progressively improve the approximation of negative data. Thus, the class boundary  eventually converges to the true boundary of the positive class in the feature space. We present the M-C algorithm with supporting  theoretical and experimental justifications. Our experiments show that, given the same set of positive examples, the M-C algorithm  outperforms one-class SVMs, and it is almost as accurate as the traditional SVMs.
Mining Sequential Patterns by Pattern%2DGrowth The PrefixSpan Approach.
 Sequential pattern mining is an important data mining problem with broad applications. However, it is also a difficult problem since the mining may have to generate or examine a combinatorially explosive number of intermediate subsequences. Most of the previously developed sequential pattern mining methods, such as GSP, explore a candidate generation-and-test approach [1] to reduce the number of candidates to be examined. However, this approach may not be efficient in mining large sequence databases having numerous patterns and/or long patterns. In this paper, we propose a projection-based, sequential pattern-growth approach for efficient mining of sequential patterns. In this approach, a sequence database is recursively projected into a set of smaller projected databases, and sequential patterns are grown in each projected database by exploring only locally frequent fragments. Based on an initial study of the pattern growth-based sequential pattern mining, FreeSpan [8], we propose a more efficient method, called PSP, which offers ordered growth and reduced projected databases. To further improve the performance, a pseudoprojection technique is developed in PrefixSpan. A comprehensive performance study shows that PrefixSpan, in most cases, outperforms the a priori-based algorithm GSP, FreeSpan, and SPADE [29] (a sequential pattern mining algorithm that adopts vertical data format), and PrefixSpan integrated with pseudoprojection is the fastest among all the tested algorithms. Furthermore, this mining methodology can be extended to mining sequential patterns with user-specified constraints. The high promise of the pattern-growth approach may lead to its further extension toward efficient mining of other kinds of frequent patterns, such as frequent substructures.  
Mining Constrained Gradients in Large Databases.
Many data analysis tasks can be viewed as search or mining in a multidimensional space (MDS). In such MDSs, dimensions capture potentially important factors for given applications, and cells represent combinations of values for the factors. To systematically analyze data in MDS, an in-teresting notion, called “cubegrade ” was recently introduced by Imielinski, et al. [IKA02], which focuses on the notable changes in measures in MDS by comparing a cell (which we refer as probe cell) with its gradient cells, namely its ancestors, descendants and siblings. We call such queries gradient analysis queries (GQs). Since an MDS can contain billions of cells, it is important to answer GQs efficiently. In this study, we focus on developing efficient methods for mining GQs constrained by certain (weakly) anti-monotone constraints. Instead of conducting an independent gradient-cell search once per probe cell, which is inefficient due to much repeated work, we propose an efficient algorithm, LiveSet-Driven. This algorithm finds all good gradient-probe cell pairs in one search pass. It utilizes measure-value analysis and dimension-match analysis in a set-oriented manner, to achieve bi-directional pruning between the sets of hopeful probe cells and of hopeful gradient cells. Moreover, it adopts a hyper-tree structure and an H-cubing
From Sequential Pattern Mining to Structured Pattern Mining A Pattern%2DGrowth Approach.

Mining Condensed Frequent%2DPattern Bases.
Frequent pattern mining has been studied extensively. However, the effectiveness and efficiency of this mining is often limited, since the number of frequent patterns generated is often too large. In many applications it is sufficient to generate and examine only frequent patterns with support frequency in close-enough approximation instead of in full precision. Such a compact but close-enough frequent pattern base is called a condensed frequent patterns-base.
The third SIGKDD workshop on mining temporal and sequential data %28KDD%2FTDM 2004%29.

Text classification from positive and unlabeled documents.
Most existing studies of text classification assume that the training data are completely labeled. In reality, however, many information retrieval problems can be more accurately described as learning a binary classifier from a set of incompletely labeled examples, where we typically have a small number of labeled positive examples and a very large number of unlabeled examples. In this paper, we study such a problem of performing Text Classification WithOut labeled Negative data (TC-WON). In this paper, we explore an efficient extension of the standard Support Vector Machine (SVM) approach, called SVMC (Support Vector Mapping Convergence) [17], for the TC-WON tasks. Our analyses show that when the positive training data is not too under-sampled, SVMC significantly outperforms other methods because SVMC basically exploits the natural &#034;gap&#034; between positive and negative documents in the feature space, which eventually corresponds to improving the generalization performance. In the text domain there are likely to exist many gaps in the feature space because a document is usually mapped to a sparse and high dimensional feature space. However, as the number of positive training data decreases, the boundary of SVMC starts overfitting at some point and end up generating very poor results. This is because when the positive training data is too few, the boundary over-iterates and trespasses the natural gaps between positive and negative class in the feature space and thus ends up fitting tightly around the few positive training data.
Discovering Compact and Highly Discriminative Features or Feature Combinations of Drug Activities Using Support Vector Machines.
Nowadays, high throughput experimental techniques make it feasible to examine and collect massive data at the molecular level. These data, typically mapped to a very high dimensional feature space, carry rich information about functionalities of certain chemical or biological entities and can be used to infer valuable knowledge for the purposes of classification and prediction. Typically, a small number of features or feature combinations may play determinant roles in functional discrimination. The identification of such features or feature combinations is of great importance. In this paper, we study the problem of discovering compact and highly discriminative features or feature combinations from a rich feature collection. We employ the support vector machine as the classification means and aim at finding compact feature combinations. Comparing to previous methods on feature selection, which identify features solely based on their individual roles in the classification, our method is able to identify minimal feature combinations that ultimately have determinant roles in a systematic fashion. Experimental study on drug activity data shows that our method can discover descriptors that are not necessarily significant individually but are most significant collectively.
Mining Typical Preferences of Collaborative User Groups.

Pushing Aggregate Constraints by Divide%2Dand%2DApproximate.
Iceberg-cube mining is to compute the GROUP BY partitions, for all GROUP BY dimension lists, that satisfy a given aggregate constraint. Previous works have pushed anti-monotone constraints into iceberg-cube mining. However, many useful constraints are not anti-monotone. In this paper, we propose a novel strategy for pushing general aggregate constraints, called Divide-and-Approximate. This strategy divides the search space and approximates the constraint in subspaces by a pushable constraint. As the strategy is recursively applied, the approximation approaches the given constraint and the pruning tights up. We show that all constraints defined by SQL aggregates, arithmetic operators and comparison operators can be pushed by Divideand -Approximate. We present an efficient implementation for an important subclass and evaluate it on both synthetic and real life databases.
TSP Mining Top%2DK Closed Sequential Patterns.
Sequential pattern mining has been studied extensively in data mining community. Most previous studies require the specification of a minimum support threshold to perform the mining. However, it is difficult for users to provide an appropriate threshold in practice. To overcome this difficulty, we propose an alternative task: mining top-k frequent closed sequential patterns of length no less than ##### , where # is the desired number of closed sequential patterns to be mined, and##### # is the minimum length of each pattern. We mine closed patterns since they are compact representations of frequent patterns.
CoMine Efficient Mining of Correlated Patterns.
Association rule mining often generates a huge number of rules, but a majority of them either are redundant or do not reflect the true correlation relationship among data objects. In this paper, we re-examine this problem and show that two interesting measures, all confidence (denoted as #) and coherence (denoted as #), both disclose genuine correlation relationships and can be computed e#ciently. Moreover, we propose two interesting algorithms, CoMine(#) and CoMine(#), based on extensions of a pattern-growth methodology. Our performance study shows that the CoMine algorithms have high performance in comparison with their Apriori-based counterpart algorithms.
Object Matching for Information Integration A Profiler%2DBased Approach.
Object matching is a fundamental problem that arises in numerous  information integration scenarios. Virtually all existing  solutions to this problem have assumed that the objects  to be matched share the same set of attributes, and that  they can be matched by comparing the similarities of the attributes.
Mining concept%2Ddrifting data streams using ensemble classifiers.
Recently, mining data streams with concept drifts for actionable insights has become an important and challenging task for a wide range of applications including credit card fraud protection, target marketing, network intrusion detection, etc. Conventional knowledge discovery tools are facing two challenges, the overwhelming volume of the streaming data, and the concept drifts. In this paper, we propose a general framework for mining concept-drifting data streams using weighted ensemble classifiers. We train an ensemble of classification models, such as C4.5, RIPPER, naive Bayesian, etc., from sequential chunks of the data stream. The classifiers in the ensemble are judiciously weighted based on their expected classification accuracy on the test data under the time-evolving environment. Thus, the ensemble approach improves both the efficiency in learning the model and the accuracy in performing classification. Our empirical study shows that the proposed methods have substantial advantage over single-classifier approaches in prediction accuracy, and the ensemble framework is effective for a variety of classification models.
CLOSET  searching for the best strategies for mining frequent closed itemsets.
Mining frequent closed itemsets provides complete and nonredundant results for frequent pattern analysis. Extensive studies have proposed various strategies for efficient frequent closed itemset mining, such as depth-first search vs. breadthfirst search, vertical formats vs. horizontal formats, treestructure vs. other data structures, top-down vs. bottomup traversal, pseudo projection vs. physical projection of conditional database, etc. It is the right time to ask “what are the pros and cons of the strategies? ” and “what and how can we pick and integrate the best strategies to achieve higher performance in general cases?” In this study, we answer the above questions by a systematic study of the search strategies and develop a winning algorithm CLOSET+. CLOSET+ integrates the advantages of the previously proposed effective strategies as well as some ones newly developed here. A thorough performance study on synthetic and real data sets has shown the advantages of the strategies and the improvement of CLOSET+ over existing mining algorithms, including CLOSET, CHARM and OP, in terms of runtime, memory usage and scalability.
CloseGraph mining closed frequent graph patterns.
Categories and Subject Descriptors
Classifying large data sets using SVMs with hierarchical clusters.

How Can Data Mining Help Bio%2DData Analysis%3F
Jiawei Han  Department of Computer Science University of Illinois at Urbana-Champaign  hanj@cs.uiuc.edu ABSTRACT  Recent progres in data mining res55C h has led to the development of numerous e#cient ands calable methods for mining interes6w9 patterns in largedatabas8w In the mean time, recent progres in biology, medicalsicalwC and DNA technologyhas led to the accumulation oftremendous amounts of bio-medical data that demands for in-depth analyshw The ques4C4 becomes howto bridge the two fields data mining  and bioinformatics, for swW2W11w9 mining of bio-medical data. In this absW]7]w e analyze ho data mining may help bio-medical data analysC and outlinesli res157 h problems  that may motivate the further developments of data mining tools for bio-data analysaw  Keywords  Bio-medical data analys5w data mining,bioinformatics data mining applications res6W4 h challenges  1. 
CPAR Classification based on Predictive Association Rules.
Recent studies in data mining have proposed a new classification approach, called associative classification, which, according to several reports, such as [7, 6], achieves higher classification accuracy than traditional classification approaches such as C4.5. However, the approach also su#ers from two major deficiencies: (1) it generates a very large number of association rules, which leads to high processing overhead; and (2) its confidence-based rule evaluation measure may lead to overfitting.
CloSpan Mining Closed Sequential Patterns in Large Databases.

Star%2DCubing Computing Iceberg Cubes by Top%2DDown and Bottom%2DUp Integration.
Data cube computation is one of the most essential but expensive operations in data warehousing. Previous studies have developedtwo major approaches, top-down vs. bottomup. The former, represented by the MultiWay Array Cube (called MultiWay) algorithm[25], aggregates simultaneously on multipledimensions
A Framework for Clustering Evolving Data Streams.
The clustering problem is a difficult problem for the data stream domain. This is because the large volumes of data arriving in a stream renders most traditional algorithms too inefficient. In recent years, a...
Profile%2DBased Object Matching for Information Integration.
matching methods rely on similarities among shared attributes. Profile-Based Object Matching builds on this approach but also correlates disjoint attributes to improve matching accuracy.
Efficient Mining of Intertransaction Association Rules.

Pushing Support Constraints Into Association Rules Mining.
Interesting patterns often occur at varied levels of support. The classic association mining  based on a uniform minimum support, such as Apriori, either misses interesting patterns of low  support or suffers from the bottleneck of itemset generation caused by a low minimum support.  A better solution lies in exploiting support constraints, which specify what minimum support  is required for what itemsets, so that only the necessary itemsets are generated. In this paper,  we present a framework of frequent itemset mining in the presence of support constraints. Our  approach is to &#034;push&#034; support constraints into the Apriori itemset generation so that the &#034;best&#034;  minimum support is determined for each itemset at run time to preserve the essence of Apriori.  This strategy is called Adaptive Apriori. Experiments show that Adaptive Apriori is highly effective  in dealing with the bottleneck of itemset generation.  Keywords. Association rules, constraints, data mining, frequent itemsets, knowledge discovery. 1 
Cancer classification using gene expression data.
The classification of different tumor types is of great importance in cancer diagnosis and drug discovery. However, most previous cancer classification studies are clinical-based and have limited diagnostic ability. Cancer classification using gene expression data is known to contain the keys for addressing the fundamental problems relating to cancer diagnosis and drug discovery. The recent advent of DNA microarray technique has made simultaneous monitoring of thousands of gene expressions possible. With this abundance of gene expression data, researchers have started to explore the possibilities of cancer classification using gene expression data. Quite a number of methods have been proposed in recent years with promising results. But there are still a lot of issues which need to be addressed and understood. In order to gain deep insight into the cancer classification problem, it is necessary to take a closer look at the problem, the proposed solutions and the related issues all together. In this survey paper, we present a comprehensive overview of various proposed cancer classification methods and evaluate them based on their computation time, classification accuracy and ability to reveal biologically meaningful gene information. We also introduce and evaluate various proposed gene selection methods which we believe should be an integral preprocessing step for cancer classification. In order to obtain a full picture of cancer classification, we also discuss several issues related to cancer classification, including the biological significance vs. statistical significance of a cancer classifier, the asymmetrical classification errors for cancer classifiers, and the gene contamination problem.
Proceedings of the Second SIAM International Conference on Data Mining

How Can Data Mining Help Bio%2DData Analysis%3F
Jiawei Han  Department of Computer Science University of Illinois at Urbana-Champaign  hanj@cs.uiuc.edu ABSTRACT  Recent progres in data mining res55C h has led to the development of numerous e#cient ands calable methods for mining interes6w9 patterns in largedatabas8w In the mean time, recent progres in biology, medicalsicalwC and DNA technologyhas led to the accumulation oftremendous amounts of bio-medical data that demands for in-depth analyshw The ques4C4 becomes howto bridge the two fields data mining  and bioinformatics, for swW2W11w9 mining of bio-medical data. In this absW]7]w e analyze ho data mining may help bio-medical data analysC and outlinesli res157 h problems  that may motivate the further developments of data mining tools for bio-data analysaw  Keywords  Bio-medical data analys5w data mining,bioinformatics data mining applications res6W4 h challenges  1. 
Mining sequential patterns with constraints in large databases.
Constraints are essential for many sequential pattern mining applications. However, there is no systematic study on constraint-based sequential pattern mining. In this paper, we investigate this issue and point out that the framework developed for constrained frequent-pattern mining does not fit our missions well. An extended framework is developed based on a sequential pattern growth methodology. Our study shows that constraints can be effectively and efficiently pushed deep into sequential pattern mining under this new framework. Moreover, this framework can be extended to constraint-based structured pattern mining as well.
Online Analytical Processing Stream Data Is It Feasible%3F
Real-time surveillance systems and other dynamic environ- ments often generate tremendous (potentially infinite) vol- ume of stream data: the volume is too huge to be scanned multiple times. However, much of such data resides at rather low level of abstraction, whereas most analysts are interested in dynamic changes (such as trends and outliers) at relatively high levels of abstraction. To discover such high level characteristics, one may need to perform on-line multi-level analysis of stream data, similar to OLAP (on-line analytical processing) of relational or data warehouse data.
Profit Mining From Patterns to Actions.
A major obstacle in data mining applications is the gap between  the statistic-based pattern extraction and the value-based decision  making. We present a profit mining approach to reduce this gap. In profit  mining, we are given a set of past transactions and pre-selected target  items, and we like to build a model for recommending target items and  promotion strategies to new customers, with the goal of maximizing the  net profit. We identify several issues in profit mining and propose solutions.
Mining Top%2DK Frequent Closed Patterns without Minimum Support.
In this paper, we propose a new mining task: mining top-k frequent closed patterns of length no less than min_l, where k is the desired number of frequent closed patterns to be mined, and min_l is the minimal length of each pattern. An efficient algorithm, called TFP, is developed for mining such patterns without minimum support. Two methods, closed_node_count and descendant_sum are proposed to effectively raise support threshold and prune FP-tree both during and after the construction of FP-tree. During the mining process, a novel top-down and bottom-up combined FP-tree mining strategy is developed to speed-up support-raising and closed frequent pattern discovering. In addition, a fast hash-based closed pattern verification scheme has been employed to check efficiently if a potential closed pattern is really closed. Our...
On Computing Condensed Frequent Pattern Bases.
Frequent pattern mining has been studied extensively. However, the effectiveness and efficiency of this mining is often limited, since the number of frequent patterns generated is often too large. In many applications it is sufficient to generate and examine only frequent patterns with support frequency in close-enough approximation instead of in full precision. Such a compact but close-enough frequent pattern base is called a condensed frequent patterns-base.
Heterogeneous Learner for Web Page Classification.
Classification of an interesting class of Web pages (e.g., personal homepages, resume pages) has been an interesting problem. Typical machine learning algorithms for this problem require two classes of data for training: positive and negative training examples. However, in application to Web page classification, gathering an unbiased sample of negative examples appears to be difficult. We propose a heterogeneous learning framework for classifying Web pages, which (1) eliminates the need for negative training data, and (2) increases classification accuracy by using two heterogeneous learners. Our framework uses two heterogeneous learners -- a decision list and a linear separator which complement each other -- to eliminate the need for negative training data in the training phase and to increase the accuracy in the testing phase. Our results show that our heterogeneous framework achieves high accuracy without requiring negative training data; it enhances the accuracy of linear separators by reducing the errors on &#034;low-margin data&#034;. That is, it classifies more accurately while requiring less human efforts in training.
gSpan Graph%2DBased Substructure Pattern Mining.
We investigate new approaches for frequent graph-based pattern mining in graph datasets and propose a novel algorithm called gSpan (graph-based Substructure pattern mining) , which discovers frequent substructures without candidate generation. gSpan builds a new lexicographic order among graphs, and maps each graph to a unique minimum DFS code as its canonical label. Based on this lexicographic order, gSpan adopts the depth-first search strategy to mine frequent connected subgraphs efficiently. Our performance study shows that gSpan substantially outperforms previous algorithms, sometimes by an order of magnitude.
Mining frequent item sets by opportunistic projection.
In this paper, we present a novel algorithm OpportuneProject for mining complete set of frequent item sets by projecting databases to grow a frequent item set tree. Our algorithm is fundamentally different from those proposed in the past in that it opportunistically chooses between two different structures, arraybased or tree-based, to represent projected transaction subsets, and heuristically decides to build unfiltered pseudo projection or to make a filtered copy according to features of the subsets. More importantly, we propose novel methods to build tree-based pseudo projections and array-based unfiltered projections for projected transaction subsets, which makes our algorithm both CPU time efficient and memory saving. Basically, the algorithm grows the frequent item set tree by depth first search, whereas breadth first search is used to build the upper portion of the tree if necessary. We test our algorithm versus several other algorithms on real world datasets, such as BMS-POS, and on IBM artificial datasets. The empirical results show that our algorithm is not only the most efficient on both sparse and dense databases at all levels of support threshold, but also highly scalable to very large databases.
PEBL positive example based learning for Web page classification using SVM.
for Web mining. Specifically, classifying Web pages of a user-interesting class is the first step of mining interesting information from the Web. However, constructing a classifier for an interesting class requires laborious pre-processing such as collecting positive and negative training examples. For instance, in order to construct a &#034;homepage&#034; classifier, one needs to collect a sample of homepages (positive examples) and a sample of non-homepages (negative examples). In particular, collecting negative training examples requires arduous work and special caution to avoid biasing them. We introduce in this paper the Positive Example Based Learn- ing (PEBL) framework for Web page classification which eliminates the need for manually collecting negative training examples in pre-processing. We present an algorithm called Mapping-Convergence (M-C) that achieves classification accuracy (with positive and unlabeled data) as high as that of traditional SVM (with positive and negative data). Our experiments show that when the M-C algorithm uses the same amount of positive examples as that of traditional SVM, the M-C algorithm performs as well as traditional SVM.
Top Down FP%2DGrowth for Association Rule Mining.

Mining long sequential patterns in a noisy environment.
many applications including computational biology study, consumer behavior analysis, system performance analysis, etc. In a noisy environment, an observed sequence may not accurately reflect the underlying behavior. For example, in a protein sequence, the amino acid N is likely to mutate to D with little impact to the biological function of the protein. It would be desirable if the occurrence of D in the observation can be related to a possible mutation from N in an appropriate manner. Unfortunately, the support measure (i.e., the number of occurrences) of a pattern does not serve this purpose. In this paper, we introduce the concept of compatibility matrix as the means to provide a probabilistic connection from the observation to the underlying true value. A new metric match is also proposed to capture the &#034;real support&#034; of a pattern which would be expected if a noise-free environment is assumed. In addition, in the context we address, a pattern could be very long. The standard pruning technique developed for the market basket problem may not work efficiently. As a result, a novel algorithm that combines statistical sampling and a new technique (namely border collapsing) is devised to discover long patterns in a minimal number of scans of the sequence database with sufficiently high confidence. Empirical results demonstrate the robustness of the match model (with respect to the noise) and the efficiency of the probabilistic algorithm.
CubeExplorer online exploration of data cubes.

Multi%2DDimensional Regression Analysis of Time%2DSeries Data Streams.
Real-time production systems and other dynamic environments often generate tremendous (potentially infinite) amount of stream data; the volume of data is too huge to be stored on disks or scanned multiple times. Can we perform on-line, multi-dimensional analysis and data mining of such data to alert people about dramatic changes of situations and to initiate timely, high-quality responses? This is a challenging task. In this paper,
Quotient Cube How to Summarize the Semantics of a Data Cube.
Partitioning a data cube into sets of cells with &#034;similar behavior&#034; often better exposes the semantics in the cube. E.g., if we find that average boots sales in the West 10th store of Walmart was the same for winter as for the whole year, it signifies something interesting about the trend of boots sales in that location in that year. In this paper, we are interested in finding succinct summaries of the data cube, exploiting regularities present in the cube, with a clear basis. We would like the summary: (i) to be as concise as possible, (it) to itself form a lattice preserving the rollup/drilldown semantics of the cube, and (iii) to allow the original cube to be fully recovered.
Emerging scientific applications in data mining.
and store data, mine for new hypotheses, confirm with data or supplemental experiment.&#034; The long-term significance of the new data of molecular biology is that it can be combined with clinical medical data to achieve a higher-resolution understanding of the causes for and treatment of disease. A major challenge for data mining in biomedicine is therefore the organization of molecular data, cellular data, and clinical data in ways allowing them to be integrated for the sake of knowledge extraction.  A major additional source of information is the published medical literature, increasingly available online in full-text form or as useful (but unstructured) summaries of the main data and biomedical hypotheses.  Telecommunications  Data mining flourishes in telecommunications due to the availability of vast quantities of high-quality data. A significant stream of it consists of call records collected at network switches used primarily for EMERGING  SCIENTIFIC  APPLICATIONS IN DATA MINING  A
Data Mining for Web Intelligence.
Data mining holds the key to uncovering and...
CLARANS A Method for Clustering Objects for Spatial Data Mining.
Abstract — This paper describes the results of a novel research and development effort conducted at the NASA Ames Research Center for discovering anomalies in discrete parameter sequences recorded from flight data 1 2.Many of the discrete parameters that are recorded during the flight of a commercial airliner correspond to binary switches inside the cockpit. The inputs to our system are records from thousands of flights for a given class of aircraft and destination. The system delivers a list of potentially anomalous flights as well as reasons why the flight was tagged as anomalous. This output can be analyzed by safety experts to determine whether or not the anomalies are indicative of a problem that could be addressed with a human factors intervention. The final goal of the system is to help safety experts discover significant human factors issues such as pilot mode confusion, i.e., a flight in which a pilot has lost situational awareness as reflected in atypicality of the sequence of switches that he or she throws during descent compared to a population of similar flights. We view this work as an extension of Integrated System Health Management (ISHM) where the goal is to understand and evaluate the combined health of a class of aircraft at a given destination. 1.
Constrained frequent pattern mining a pattern%2Dgrowth view.

Database Research at the University of Illinois at Urbana%2DChampaign.

A template model for multidimensional inter%2Dtransactional association rules.

Multi%2DDimensional Sequential Pattern Mining.
With our recently developed sequential pattern mining algorithms, such as PrefixSpan, it is possible to mine sequential user-access patterns from Web-logs. While this information is very useful when redesigning web-sites for easier perusal and fewer network traffic bottlenecks, it would be so much richer if we could incorporate multiple dimensions of information. For example, if you knew the referral site that users frequently come from, you might be able to determine what information on your own web-site is of interest to them --- and enhance or separate this information as needed.  Similarly, if you knew what weekday and time certain access patterns frequently occur at, you could ensure updated information is ready and available for these users.  This thesis proposes and explores two different techniques, HYBRID and PSFP, to incorporate additional dimensions of information into the process of mining sequential patterns. It investigates the strengths and limitations of each approach. The HYBRID method first finds frequent dimension value combinations, and then mines sequential  patterns from the set of sequences that satisfy each of these combinations. PSFP approaches the problem from the opposite direction. It mines the sequential patterns for the whole dataset only once (using PrefixSpan), and mines the corresponding frequent dimension patterns alongside each sequential pattern (using existing association algorithm FP-growth). Experiments show that HYBRID is most effective at low support in datasets that are sparse with respect to dimension value combinations but dense with respect to the sequential patterns present. PSFP is the better alternative in every other case, including datasets that are dense with respect to both dimension values combinations and sequential ...
Fault%2DTolerant Frequent Pattern Mining Problems and Challenges.

RecTree An Efficient Collaborative Filtering Method.
Abstract. Many people rely on the recommendations of trusted friends to find restaurants or movies, which match their tastes. But, what if your friends have not sampled the item of interest? Collaborative filtering (CF) seeks to increase the effectiveness of this process by automating the derivation of a recommendation, often from a clique of advisors that we have no prior personal relationship with. CF is a promising tool for dealing with the information overload that we face in the networked world. Prior works in CF have dealt with improving the accuracy of the predictions. However, it is still challenging to scale these methods to large databases. In this study, we develop an efficient collaborative filtering method, called RecTree (which stands for RECommendation Tree) that addresses the scalability problem with a divide-and-conquer approach. The method first performs an efficient k-means-like clustering to group data and creates neighborhood of similar users, and then performs subsequent clustering based on smaller, partitioned databases. Since the progressive partitioning reduces the search space dramatically, the search for an advisory clique will be faster than scanning the entire database of users. In addition, the partitions contain users that are more similar to each other than those in other partitions. This characteristic allows RecTree to avoid the dilution of opinions from good advisors by a multitude of poor advisors and thus yielding a higher overall accuracy. Based on our experiments and performance study, RecTree outperforms the well-known collaborative filter, CorrCF, in both execution time and accuracy. In particular, RecTree&#039;s execution time scales by O(nlog 2 (n)) with the dataset size while CorrCF scales quadratically. 1
PrefixSpan Mining Sequential Patterns by Prefix%2DProjected Growth.

Spatial Clustering in the Presence of Obstacles.
Clustering in spatial data mining is to group similar objects based on their distance, connectivity, or their relative density in space. In the real world, there exist many physical obstacles such as rivers, lakes and high-ways, and their presence may affect the result of clus-tering substantially. In this paper, we study the problem of clustering in the presence of obstacles and define it as a COD (Clustering with Obstructed Distance) prob-lem. As a solution to this problem, we propose a scal-able clustering algorithm, called COD-CLARANS. We discuss various forms of pre-processed information that could enhance the eficiency of COD-CLARANS. In the strictest sense, the CODproblem can be treated as a change an distance function and thus could be handled by current clustering algorithms by changing the dis-tance function. However, we show that by pushing the task of handling obstacles into COD-CLARANS instead of abstracting it at the distance function level, more op-timization can be done in the form of a pruning func-tion E’. We conduct various performance studies to show that COD-CLARANS is both eficient and effec-tive. 1
Mining Frequent Item Sets with Convertible Constraints.

CMAR Accurate and Efficient Classification Based on Multiple Class%2DAssociation Rules.

H%2DMine Hyper%2DStructure Mining of Frequent Patterns in Large Databases.
Methods for efficient mining of frequent patterns have been studied extensively by many researchers. However, the previously proposed methods still encounter some performance bottlenecks when mining databases with different data characteristics, such as dense vs. sparse, long vs. short patterns, memory-based vs. disk-based, etc.
Constraint%2Dbased clustering in large databases.
. Constrained clustering| nding clusters that satisfy user-speci ed constraints|is highly desirable in many applications. In this paper, we introduce the constrained clustering problem and show that traditional clustering algorithms (e.g., k-means) cannot handle it. A scalable constraint-clustering algorithm, Coca, is developed in this study which starts by nding an initial solution that satis es user-speci ed constraints and then re nes the solution by performing con ned object movements under constraints. Our algorithm consists of two phases: pivot movement and deadlock resolution. For both phases, we show that nding the optimal solution is NP-hard. We then propose several heuristics and show how our algorithm can scale up for large data sets using the heuristic of micro-cluster sharing. By experiments, we show the eectiveness and eciency of the heuristics. 1
Mining top%2Dn local outliers in large databases.
Outlier detection is an important task in data mining with numerous applications, including credit card fraud detection, video surveillance, etc. A recent work on outlier detection has introduced a novel notion of local outlier in which the degree to which an object is outlying is dependant on the density of its local neighborhood, and each object can be assigned a Local Outlier Factor (LOF) which represents the likelihood of that object being an outlier. Although the concept of local outliers is a useful one, the computation of LOFvalues for every data objects requires a large number of k-nearest neighbors searches and can be computationally expensive. Since most objects are usually not outliers, it is useful to provide users with the option of finding only n most outstanding local outliers, i.e., the top-n data objects which are most likely to be local outliers according to their LOFs. However, if the pruning is not done carefully, finding top-n outliers could result in the same amount of computation as finding LOFfor all objects. In this paper, we propose a novel method to efficiently find the top-n local outliers in large databases. The concept of &#034;micro-cluster&#034; is introduced to compress the data. An efficient micro-cluster-based local outlier mining algorithm is designed based on this concept. As our algorithm can be adversely affected by the overlapping in the micro-clusters, we proposed a meaningful cut-plane solution for overlapping data. The formal analysis and experiments show that this method can achieve good performance in finding the most outstanding local outliers .
Scalable frequent%2Dpattern mining methods an overview.

Efficient Computation of Iceberg Cubes with Complex Measures.
 It is often too expensive to compute and materialize a complete high-dimensional data cube. Computing an iceberg cube, which contains only aggregates above certain thresholds, is an effective way to derive nontrivial multidimensional aggregations for OLAP and data mining. In this paper, we study efficient methods for computing iceberg cubes with some popularly used complex measures, such as average, and develop a methodology that adopts a weaker but anti-monotonic condition for testing and pruning search space. In particular, for efficient computation of iceberg cubes with the average measure, we propose a top-k average pruning method and extend two previously studied methods, Apriori and BUC, to Top-k Apriori and Top-k BUC. To further improve the performance, an interesting hypertree structure, called H-tree, is designed and a new iceberg cubing method, called Top-k H-Cubing, is developed. Our performance study shows that Top-k BUC and Top-k H-Cubing are promising candidates for scalable computation, and Top-k H-Cubing has the best performance in many cases. 
DNA%2DMiner A System Prototype for Mining DNA Sequences.

Mining Multi%2DDimensional Constrained Gradients in Data Cubes.
1 Introduction In recent years, there have been growing interests in multi-dimensional analysis of relational databases, transactional
Reminiscences on Influential Papers.

Data Mining Concepts and Techniques
• Introducing the concept of a warehouse, modeling of data and schemas used.
CLOSET An Efficient Algorithm for Mining Frequent Closed Itemsets.
Association mining may often derive an undesirably large set of frequent itemsets and association rules. Recent studies have proposed an interesting alternative: mining frequent closed itemsets and their corresponding rules, which has the same power as association mining but substantially reduces the number of rules to be presented. In this paper, we propose an efficient algorithm, CLOSET, for mining closed itemsets, with the development of three techniques: (1) applying a compressed, frequent pattern tree FP-tree structure for mining closed itemsets without candidate generation, (2) developing a single prefix path compression technique to identify frequent closed itemsets quickly, and (3) exploring a partition-based projection mechanism for scalable mining in large databases. Our performance study shows that CLOSET is efficient and scalable over large databases, and is faster than the previously proposed methods. 1 Introduction It has been well recognized that frequent pattern minin...
AIM Approximate Intelligent Matching for Time Series Data.

Mining Recurrent Items in Multimedia with Progressive Resolution Refinement.
Despite the overwhelming amounts of multimedia data recently generated and the significance of such data, very few people have systematically investigated multimedia data mining. With our previous studies on content-based retrieval of visual artifacts, we study in this paper the methods for mining content-based associations with recurrent items and with spatial relationships from large visual data repositories. A progressive resolution refinement approach is proposed in which frequent item-sets at rough resolution levels are mined, and progressively, finer resolutions are mined only on the candidate frequent item-sets derived from mining rough resolution levels. Such a multi-resolution mining strategy substantially reduces the overall data mining cost without loss of the quality and completeness of the results.
Can we push more constraints into frequent pattern mining%3F

FreeSpan frequent pattern%2Dprojected sequential pattern mining.
Mining frequent patterns from large databases plays an essential role in many data mining tasks and has broad applications. Most of the previously proposed methods adopt apriorilike candidate-generation-and-test approaches. However, those methods may encounter serious challenges when mining datasets with prolific patterns and/or long patterns. In this
Geo%2DSpatial Clustering with User%2DSpecified Constraints.
Duminda Wijesekera and Daniel Barbara  15:00-16:00 Session 4 (Discussion)  . 15:00-15:15 Variations on Multimedia Data Mining Simeon J. Simoff  . 15:15-16:00 Discussion: What does Multimedia Mining encompass and what are the open issues  16:00-16:30 Coffee break  16:30 - 19:00 SIGKDD&#039;2000 Conference Opening and awards  viii  ix  Table of Contents  Geo-Spatial Clustering with User-Specified Constraints Anthony K.H. Tong, Raymond T. Ng, Laks V.S. Lakshmanan, Jiawei Han ...................... 1 Multi-level Indexing and GIS Enhanced Learning for Satellite Imageries Krzysztof Koperski, Giovanni B. Marchisio ............................................................8 Predicting Locations Using Map Similarity(PLUMS): A Framework for Spatial Data Mining. Sanjay Chawla, Shashi Shekhar, Weili Wu, Uygar Ozesmi ..........................................14 Learning Prosodic Patterns for Mandarin Speech Synthesis Yiqiang Chen, Wen Gao, Tingshao Zhu ..................................................
COE Clustering with Obstacles Entities. A Preliminary Study.

Mining Access Patterns Efficiently from Web Logs.
With the explosive growth of data available on the World Wide Web, discovery and analysis of useful information from the World Wide Web becomes a practical necessity.Web access pattern, which is the sequence of accesses pursued by users frequently, is a kind of interesting and useful knowledge in practice. In this paper, we study the problem of mining access patterns from Web logs efficiently. A novel data structure, called Web access pattern tree, or WAP-tree in short, is developed for efficient mining of access patterns from pieces of logs. The Web access pattern tree stores highly compressed, critical information for access pattern mining and facilitates the developmentofnovel algorithms for mining access patterns in large set of log pieces. Our algorithm can find access patterns from Web logs quite efficiently. The experimental and performance studies show that our method is in general an order of magnitude faster than conventional methods.
Mining Frequent Patterns without Candidate Generation.
In this paper, we propose a novel data structure called CATS Tree. CATS Tree extends the idea of FPTree to improve storage compression and allow frequent pattern mining without generation of candidate itemsets. The proposed algorithms enable frequent pattern mining with different supports without rebuilding the tree structure. Furthermore, the algorithms allow mining with a single pass over the database as well as efficient insertion or deletion of transactions at any time.
Mining Frequent Itemsets Using Support Constraints.
Interesting patterns often occur at varied levels  of support. The classic association mining  based on a uniform minimum support, such  as Apriori, either misses interesting patterns  of low support or suffers from the bottleneck  of itemset generation. A better solution is  to exploit support constraints, which specify  what minimum support is required for what  itemsets, so that only necessary itemsets are  generated. In this paper, we present a framework  of frequent itemset mining in the presence  of support constraints. Our approach is  to &#034;push&#034; support constraints into the Apriori  itemset generation so that the &#034;best&#034; minimum  support is used for each itemset at run  time to preserve the essence of Apriori.  1 Introduction  The association rules mining, first studied in [AIS93, AS94] for market-basket analysis, is to find all association rules above some user-specified minimum support and minimum confidence. The bottleneck of this problem is finding frequent itemsets (and supp...
Beyond intratransaction association analysis mining multidimensional intertransaction association rules.

Object%2DBased Selective Materialization for Efficient Implementation of Spatial Data Cubes.
... In this paper,  we study methods for spatial OLAP, by integration of nonspatial OLAP methods with spatial database implementation techniques. A  spatial data warehouse model, which consists of both spatial and nonspatial dimensions and measures, is proposed. Methods for  computation of spatial data cubes and analytical processing on such spatial data cubes are studied, with several strategies proposed,  including approximation and selective materialization of the spatial objects resulted from spatial OLAP operations. The focus of our  study is on a method for spatial cube construction, called object-based selective materialization, which is different from cuboid-based  selective materialization proposed in previous studies of nonspatial data cube construction. Rather than using a cuboid as an atomic  structure during the selective materialization, we explore granularity on a much finer level, that of a single cell of a cuboid. Several  algorithms are proposed for object-based selective materialization of spatial data cubes and the performance study has demonstrated the effectiveness of these techniques.
Efficient Rule%2DBased Attribute%2DOriented Induction for Data Mining.
. Data mining has become an important technique which has tremendous potential in many commercial and industrial applications. Attribute-oriented induction is a powerful mining technique and has been successfully implemented in the data mining system DBMiner [17]. However, its induction capability is limited by the unconditional concept generalization. In this paper, we extend the concept generalization to rule-based concept hierarchy, which enhances greatly its induction power. When previously proposed induction algorithm is applied to the more general rule-based case, a problem of induction anomaly occurs which impacts its efficiency. We have developed an efficient algorithm to facilitate induction on the rule-based case which can avoid the anomaly. Performance studies have shown that the algorithm is superior than a previously proposed algorithm based on backtracking.  Keywords: data mining, knowledge discovery in databases, rule-based concept generalization, rule-based concept hier...
Discovering Geographic Knowledge in Data Rich Environments A Report on a Specialist Meeting.

Mining Frequent Patterns by Pattern%2DGrowth Methodology and Implications.

Plan Mining by Divide%2Dand%2DConquer.
Plans or sequences of actions are an important form of data. With the proliferation of database technology, plan databases (or planbases) are increasingly common. Efficient discovery of important patterns of actions in plan databases presents a challenge to data mining. In this paper, we present a method for mining significant patterns of successful actions in a large planbase using a divide-andconquer strategy. The method exploits multi-dimensionM generalization of sequences of actions and extracts the inherent hierarchicM structure and sequential patterns of plans at different levels of abstraction. These patterns are used in turn to subsequently narrow down the search for more specific patterns. The process is anaJogous to the use of divide-and-conquer methods in hierarchicM planning. We illustrate our approach using a travel planning database.
Mining Inter%2DTransaction Associations with Templates.
Multi-dimensional, inter-transaction association rules extend the traditional association rules to describe more general associations among items with multiple properties cross transactions. &#034;After McDonald and Burger King open branches, KFC will open a branch two months later and one mile away&#034; is an example of such rules. Since the number of potential inter-transaction association rules tends to be extremely large, mining inter-transaction associations poses more challenges on efficient processing than mining intra-transaction associations. In order to make such association mining truly practical and computationally tractable, in this study, we present a template model to help users declare the interesting inter-transaction associations to be mined. With the guidance of templates, several optimization techniques are devised to speed up the discovery of inter-transaction association rules. We show, through a series of experiments, that these optimization techniques can yield significa...
Efficient Mining of Partial Periodic Patterns in Time Series Database.
Partial periodicity search, i.e., search for partial periodic patterns in time-series databases, is an interesting data mining problem. Previous studies on periodicity search mainly consider finding full periodic patterns, where every point in time contributes (precisely or approximately) to the periodicity. However, partial periodicity is very common in practice since it is more likely that only some of the time episodes may exhibit periodic patterns. We present several algorithms for efficient mining of partial periodic patterns, by exploring some interesting properties related to partial periodicity, such as the Apriori property and the max-subpattern hit set property, and by shared mining of multiple periods. The max-subpattern hit set property is a vital new property which allows us to derive the counts of all frequent patterns from a relatively small subset of patterns existing in the time series. We show that mining partial periodicity needs only two scans over the time series database, even for mining multiple periods. The performance study shows our proposed methods are very efficient in mining long periodic patterns.
Breaking the Barrier of Transactions Mining Inter%2DTransaction Association Rules.

Optimization of Constrained Frequent Set Queries with 2%2Dvariable Constraints.
Currently, there is tremendous interest in providing ad-hoc mining capabilities in database management systems. As a first step towards this goal, in [15] we proposed an architecture for supporting constraint-based, human-centered, exploratory mining of various kinds of rules including associations, introduced the notion of constrained frequent set queries (CFQs), and developed effective pruning optimizations for CFQs with 1-variable (1-var) constraints. While 1-var constraints
Exploratory Mining via Constrained Frequent Set Queries.
Although there have been many studies on data mining, to date there have been few research prototypes or commercial systems supporting comprehensive query-driven mining, which encourages interactive exploration of the data. Our thesis is that constraint constructs and the optimization they induce play a pivotal role in mining queries, thus substantially enhancing the usefulness and performance of the mining system. This is based on the analogy of dedarative query languages like SOL and query optimization which have made relational databases so successful. To this end, our proposed demo is not yet another data mining system, but of a new paradigm in data mining - mining with constraints, as the important first step towards supporting ad-hoc mining in DBMS.
Efficient Polygon Amalgamation Methods for Spatial OLAP and Spatial Data Mining.
The polygon amalgamation operation computes the boundary of the union of a set of polygons. This is an important operation for spatial on-line analytical processing and spatial data mining, where polygons representing different spatial objects often need to be amalgamated by varying criteria when the user wants to aggregate or reclassify these objects. The processing cost of this operation can be very high for a large number of polygons. Based on the observation that not all polygons to be amalgamated contribute to the boundary, we investigate in this paper efficient polygon amalgamation methods by excluding those internal polygons without retrieving them from the database. Two novel algorithms, adjacency-based and occupancy-based, are proposed.
Review %2D An Array%2DBased Algorithm for Simultaneous Multidimensional Aggregates.

Constraint%2DBased Multidimensional Data Mining.
s  . the part of the database to be mined (called the minable view    ),  . the type of pattern/rule to be mined, and  . the properties that the patterns should satisfy.  These patterns should include not only numerical constraints  on statistical properties (like support, confidence,  and correlation), but also those based on  attribute domains, classes, and aggregates,    such as  &#034;I.type = `snacks&#039; and avg(I.price) &lt; 100.&#034;  Second, a data-mining system should support efficient  processing and optimization of mining queries  by providing a sophisticated mining-query optimizer.  Such an optimizer exploits the various constraints  stated in the user-specified mining query and their  properties to generate access plans that guarantee a  level of performance commensurate with the constraints  in the query.  CONSTRAINTS: ESSENTIALS FOR AD  HOC DATA MINING  We divide constraints into five categories:  . Knowledge type constraints specify the type of  knowledge to be mined, such as concept 
Join Index Hierarchy An Indexing Structure for Efficient Navigation in Object%2DOriented Databases.
A novel indexing structure, join index hierarchy, is proposed to handle the &#034;goto&#039;s on disk&#034; problem in object-oriented query processing. The method constructs a hierarchy of join indices and transforms a sequence of pointer chasing operations into a simple search in an appropriate join index file, and thus accelerates navigation in object-oriented databases. The method extends the join index structure studied in relational and spatial databases, supports both forward and backward navigations among objects and classes, and localizes update propagations in the hierarchy. Our performance study shows that partial join index hierarchy outperforms several other indexing mechanisms in object-oriented query processing. Index Terms: index structures, join indices, query processing, query optimization, object-oriented database. 1 Introduction  Query processing and optimization is crucial to the performance of object-oriented database systems. Substantial research into query processing and query...
Mining Multiple%2DLevel Association Rules in Large Databases.
 
Discovering Web Access Patterns and Trends by Applying OLAP and Data Mining Technology on Web Logs.
As a con#uence of data mining and WWW technologies, it is now possible to perform data mining on web logrecords collectedfrom the Internet web page access history. The behaviour of the web page readers is imprinted in the web server log #les. Analyzing and exploring regularities in this behaviour can improve system performance, enhance the quality and delivery of Internet information services to the end user, and identify population of potential customers for electronic commerce. Thus, by observing people using collections of data, data mining can bring considerable contribution to digital library designers.
Mining multimedia data.
We propose a multi-wing harmonium model for mining multimedia data that extends and improves on earlier models based on two-layer random fields, which capture bidirectional  dependencies between hidden  topic aspects and observed inputs. This model can be viewed as an undirected counterpart of the two-layer directed models such  as LDA for similar tasks, but bears significant  di#erence in inference/learning cost tradeoffs, latent topic representations, and topic  mixing mechanisms. In particular, our model facilitates efficient inference and robust topic  mixing, and potentially provides high flexibilities  in modeling the latent topic spaces. A  contrastive divergence and a variational algorithm  are derived for learning. We specialized  our model to a dual-wing harmonium for  captioned images, incorporating a multivariate  Poisson for word-counts and a multivariate  Gaussian for color histogram. We present  empirical results on the applications of this  model to classification, retrieval and image  annotation on news video collections, and we  report an extensive comparison with various  extant models.
Mining Segment%2DWise Periodic Patterns in Time%2DRelated Databases.
Periodicity search, that is, search for cyclicity in time-related databases, is an interesting data mining problem. Most previous studies have been on finding full-cycle periodicity for all the segments in the selected sequences of the data, that is, if a sequence is periodic, all the points or segments in the period repeat. However, it is often useful to mine segment-wise or point-wise periodicity in time-related data sets. In this study, we integrate data cube and Apriori data mining techniques for mining segment-wise periodicity in regard to a fixed length period and show that data cube provides an efficient structure and a convenient way for interactive mining of multiple-level periodicity. Introduction  Periodicity search, that is, search for cyclic patterns in time-related data sets, is an important data mining problem with many applications. Most previously studied methods on periodicity pattern search are on mining  full-cycle periodicity in the sense that every point in the pe...
Selective Materialization An Efficient Method for Spatial Data Cube Construction.
On-line analytical processing (OLAP) has gained its popu-  larity in database industry. With a huge amount of data stored in spatial  databases and the introduction of spatial components to many relational  or object-relational databases, it is important to study the methods for  spatial data warehousing and on-line analytical processing of spatial  data. In this paper, we study methods for spatial OLAP, by integra-  tion of nonspatial on-line analytical processing (OLAP) methods with  spatial database implementation techniques. A spatial data warehouse  model, which consists of both spatial and nonspatial dimensions and  measures, is proposed. Methods for computation of spatial data cubes  and analytical processing on such spatial data cubes are studied, with  several strategies proposed, including approximation and partial materialization  of the spatial objects resulted from spatial OLAP operations.
Exploratory Mining and Pruning Optimizations of Constrained Association Rules.
From the standpoint of supporting human-centered discovery of knowledge, the present-day model of mining association rules suffers from the following serious shortcom- ings: (i) lack of user exploration and control, (ii) lack of focus, and (iii) rigid notion of relationships. In effect, this model functions as a black-box, admitting little user interaction in between. We propose, in this paper, an architecture that opens up the black-box, and supports constraintbased, human-centered exploratory mining of associations. The foundation of this architecture is a rich set of con- straint constructs, including domain, class, and $QL-style aggregate constraints, which enable users to clearly specify what associations are to be mined. We propose constrained association queries as a means of specifying the constraints to be satisfied by the antecedent and consequent of a mined association.
MultiMediaMiner A System Prototype for Multimedia Data Mining.
The DataSURG group at NDSU has a long-standing interest in data mining remotely sensed imagery (RSI) for agricultural, forestry and other prediction and analysis applications. A spatial data structure, the Peano count tree, was developed that provided an efficient, lossless, data mining ready representation of the many types of data involved in these applications. This data structure has made possible the mining of multiple very large data sets, including time-sequence of RSI and multimedia land data. The Peano count tree (P-tree) technology provides an efficient way to store and mine images of any format, together with pertinent land data of still other formats.
WebML Querying the World%2DWide Web for Resources and Knowledge.
There is a massive increase of information available on electronic networks. This profusion of resources on the World-Wide Web gave rise to considerable interest in the research community. Traditional information retrieval techniques have been applied to the document collection on the Internet, and amyriad of search engines and tools have been proposed and implemented. However, the e ectiveness of these tools is not satisfactory. None of them is capable of discovering knowledge from the Internet. We propose a declarative query language that would allow resource discovery on the Internet with interactive and progressively re ned inquiries. The language also consents to the discovery of knowledge within the content of the documents and the structure of the hyperspace.  
Generalization%2DBased Data Mining in Object%2DOriented Databases Using an Object Cube Model.
Data mining is the discovery of knowledge and useful information from the large amounts of data stored in  databases. With the increasing popularity of object-oriented database systems in advanced database applications,  it is important to study the data mining methods for object-oriented databases because mining knowledge from  such databases may improve understanding, organization, and utilization of the data stored there.
Editorial.
calls &amp; calendarEDITORIAL
Evaluation of Declarative n%2DQueens Recursion A Deductive Database Approach.

Knowledge representation and discovery based on linguistic atoms.

Towards On%2DLine Analytical Mining in Large Databases.
Great efforts have been paid in the Intelligent Database Systems Research Lab for the research and development of efficient data mining methods and construction of on-line analytical data mining systems. Our work
DBMiner a system for data mining in relational databases and data warehouses.

OLAP Mining Integration of OLAP with Data Mining.
OLAP mining is a mechanism which integrates on-line analytical processing (OLAP) with data mining so that mining can be performed in different portions of databases or data warehouses and at different levels of abstraction at user&#039;s finger tips. With rapid developments of data warehouse and OLAP technologies in database industry, it is promising to develop OLAP mining mechanisms. With our
Data Mining Where is it Heading%3F %28Panel%29.

Metarule%2DGuided Mining of Multi%2DDimensional Association Rules Using Data Cubes.
In this paper, we employ a novel approach to  metarule-guided, multi-dimensional association  rule mining which explores a data cube structure.
Generalization and Decision Tree Induction Efficient Classification in Data Mining.
Efficiency and scalability are fundamental issues concerning data mining in large databases. Although classification  has been studied extensively, few of the known methods take serious consideration of efficient induction in large databases and the analysis of data at multiple abstraction levels. This paper addresses the efficiency and scalability issues by proposing a data classification method which integrates attribute-oriented induction, relevance analysis, and the induction of decision trees. Such an integration leads to efficient, high-quality, multiple-level classification of large amounts of data, the relaxation of the requirement of perfect training sets, and the elegant handling of continuous and noisy data.
GeoMiner A System Prototype for Spatial Data Mining.
Spatial data mining is to mine high-level spatial information and knowledge from large spatial databases. A spatial data mining system prototype, GeoMiner, has been designed and developed based on our years of experience in the research and development of relational data mining system, DBMiner, and our research into spatial data mining. The data mining power of GeoMiner includes mining three kinds of rules: characteristic rules, comparison rules, and association rules, in geo-spatial databases, with a planned extension to include mining classification rules and clustering rules. The SAND (Spatial And Nonspatial Data) architecture is applied in the modeling of spatial databases, whereas GeoMiner includes the spatial data cube construction module, spatial on-line analytical processing (OLAP) module, and spatial data mining modules. A spatial data mining language, GMQL (Geo- Mining Query Language), is designed and implemented as an extension to Spatial SQL [3], for spatial data mini...
Proceedings of the Second International Conference on Knowledge Discovery and Data Mining %28KDD%2D96%29
Structured attributes have domains (value sets) that are  partially ordered sets, typically hierarchies. Such  attributes allow knowledge discovery programs to  incorporate background knowledge about hierarchical  relationships among attribute values. Inductive  generalization rules for structured attributes have been  developed that take into consideration the type of nodes  in the domain hierarchy (anchor or non-anchor) and the  type of decision rules to be generated (characteristic,  discriminant or minimum complexity). These  generalization rules enhance the ability of knowledge  discovery system INLEN-2 to exploit the semantic  content of the domain knowledge in the process of  generating hypotheses. If the dependent attribute (e.g., a  decision attribute) is structured, the system generates a  system of hierarchically organized rules representing  relationships between the values of this attribute and  independent attributes. Such a situation often occurs in  practice when the decision to be assigned to a situation  can be at different levels of abstraction (e.g., this is a  liver disease, or this is a liver cancer). Continuous  attributes (e.g., physical measurements) are quantized  into a hierarchy of values (ranges of values arranged into  different levels). These methods are illustrated by an  example concerning the discovery of patterns in world  economics and demographics.
Spatial Data Mining Progress and Challenges.
Spatial data mining, i.e., mining knowledge from large amounts of spatial data, is a highly demanding field because huge amounts of spatial data have been collected in various applications, ranging from remote sensing, to geographical information systems (GIS), computer cartography, environmental assessment and planning, etc. The collected data far exceeded human&#039;s ability to analyze. Recent studies on data mining have extended the scope of data mining from relational and transactional databases to spatial databases. This paper summarizes recent works on spatial data mining, from spatial data generalization, to spatial data clustering, mining spatial association rules, etc. It shows that spatial data mining is a promising field, with fruitful research results and many challenging issues.  1 Introduction  Advances in database technologies and data collection techniques including barcode reading, remote sensing, satellite telemetry, etc., have collected huge amounts of data in large data...
Maintenance of Discovered Association Rules in Large Databases An Incremental Updating Technique.
An incremental updating technique is developed for maintenance of the association rules discovered by database mining. There have been many studies on efficient discovery of association rules in large databases. However, it is nontrivial to maintain such discovered rules in large databases because a database may allow frequent or occasional updates and such updates may not only invalidate some existing strong association rules but also turn some weak rules into strong ones. In this study, an incremental updating technique is proposed for efficient maintenance of dis- covered association rules when new transaction data are added to a transaction database.
DBMiner A System for Mining Knowledge in Large Relational Databases.
A data mining system, DBMiner, has been developed  for interactive mining of multiple-level knowledge in  large relational databases. The system implements  a wide spectrum of data mining functions, including  generalization, characterization, association, classi#-  cation, and prediction. By incorporating several interesting  data mining techniques, including attributeoriented  induction, statistical analysis, progressive  deepening for mining multiple-level knowledge, and  meta-rule guided mining, the system provides a userfriendly,  interactive data mining environment with  good performance.
A Fast Distributed Algorithm for Mining Association Rules.
With the existence of many large transaction databases, the huge amounts of data, the high scalability of distributed systems, and the easy partition and distribution of a centralized database, it is important to investigate efficient methods for distributed mining of association rules. This study discloses some interesting relationships between locally large and globally large itemsets and proposes an interesting distributed association rule mining algorithm, FDM (Fast Distributed Mining of association rules), which generates a small number of candidate sets and substantially reduces the number of messages to be passed at mining association rules. Our performance study shows that FDM has a superior performance over the direct application of a typical sequential algorithm. Further performance enhancement leads to a few variations of the algorithm.
Data Mining Techniques.
This paper discusses an overview of data mining techniques for personalization. It discusses some of the standard techniques which are used in order to adapt and increase the ability of the system to tailor itself to specific user behavior. We discuss several such techniques such as collaborative filtering, content based methods, and content based collaborative filtering methods. We examine the specific applicability of these techniques to various scenarios and the broad advantages of each in specific situations. 1
DBMiner Interactive Mining of Multiple%2DLevel Knowledge in Relational Databases.

Attribute%2DOriented Induction in data Mining.
Attribute-oriented induction is a set-oriented database mining method which generalizes the task-relevant subset of data attribute-by-attribute, compresses it into a generalized relation, and extracts from it the general features of data. In this chapter, the power of attribute-oriented induction is explored for the extraction from relational databases of different kinds of patterns, including characteristic rules, discriminant rules, cluster description rules, and multiple-level association rules. Furthermore, it is shown that the method is efficient, robust, with wide applications, and extensible to knowledge discovery in advanced database systems, including object-oriented, deductive, and spatial database systems. The implementation status of DBMiner, a system prototype which applies the method, is also reported here. 16.1 Introduction  With an upsurge of the application demands and research activities on knowledge discovery in databases (Matheus, Chan and Piatetsky-Shapiro 1993; Pi...
Intelligent Query Answering by Knowledge Discovery Techniques.
Knowledge discovery facilitates querying database knowledge and intelligent query answering in database systems. In this paper, we investigate the application of discovered knowledge, concept hierarchies, and knowledge discovery tools for intelligent query answering in database systems. A knowledge-rich data model is constructed to incorporate discovered knowledge and knowledge discovery tools. Queries are classified into data queries and knowledge queries. Both types of queries can be answered directly by simple retrieval or intelligently by analyzing the intent of query and providing generalized, neighborhood or associated information using stored or discovered knowledge. Techniques have been developed for intelligent query answering using discovered knowledge and/or knowledge discovery tools, which includes generalization, data summarization, concept clustering, rule discovery, query rewriting, deduction, lazy evaluation, application of multiplelayered databases, etc. Our study shows that knowledge discovery substantially broadens the spectrum of intelligent query answering and may have deep implications on query answering in data- and knowledge-base systems.
Data Mining An Overview from a Database Perspective.

Index Nesting %2D An Efficient Approach to Indexing in Object%2DOriented Databases
.&lt;F3.733e+05&gt; In object-oriented database systems where the concept of the superclass-subclass is supported, an instance of a subclass is also an instance of its superclass. Consequently, the access scope of a query against a class in general includes the access scope of all its subclasses, unless specified otherwise. An index to support superclass-subclass relationship efficiently must provide efficient associative retrievals of objects from a single class or from several classes in a class hierarchy. This paper presents an efficient index called the hierarchical tree (the H-tree). For each class, an H-tree is maintained, allowing efficient search on a single class. These H-trees are appropriately linked to capture the superclass-subclass relationships, thus allowing efficient retrievals of instances from a class hierarchy. Both experimental and analytical results indicate that the H-tree is an efficient indexing structure.&lt;F7.947e+05&gt;  Key words:&lt;F3.733e+05&gt; OODB -- Indexing structur...
Mining Knowledge at Multiple Concept Levels.
Most studies on data mining have been focused at mining rules at single concept levels, i.e., either at the primitive level or at a rather high concept level. However, it is often desirable to discover knowledge at multiple concept levels. Mining knowledge at multiple levels may help database users find some interesting rules which are difficult to be discovered otherwise and view database contents at different abstraction levels and from different angles. Methods for mining knowledge at multiple concept levels can often be developed by extension of existing data mining techniques. Moreover, for efficient processing and interactive mining of multiple-level rules, it is often necessary to adopt techniques such as step-by-step generalization/specialization or progressive deepening of a knowledge mining process. Other issues, such as visual representation of knowledge at multiple levels, and &#034;redundant&#034; rule filtering, should also be studied in depth.
Normalization and Compilation of Deductive and Object%2DOriented Databases Programs for Efficient Query Evaluation.
. A normalization process is proposed to serve not only as a preprocessing stage for compilation and evaluation but also as a tool for classifying recursions. Then the query-independent compilation and chain-based evaluation method can be extended naturally to process a class of DOOD programs and queries. The query-independent compilation captures the bindings that could be difficult to be captured otherwise. The chain-based evaluation explores query constraints, integrity constraints, recursion structures, and other features of the programs with a set of interesting techniques, such as chain-following, chain-split, and constraint pushing. Therefore, with this normalization and compilation process, a class of DOOD queries can be evaluated efficiently in deductive and object-oriented databases.  Keywords: Deductive and object-oriented database, compilation, recursive query evaluation, query optimization. 1 Introduction Although recursive query evaluation has been investigated extensivel...
Advances of the DBLearn System for Knowledge Discovery in Large Databases.

Resource and Knowledge Discovery in Global Information Systems A Preliminary Design and Experiment.
With huge amounts of information connected to the global information network (Internet),  efficient and effective discovery of resource and knowledge from the &#034;global information base&#034; has become an imminent research issue, especially with the advent of the Information SuperHighway. In this article, a multiple layered database (MLDB) approach is proposed to handle the resource and knowledge discovery in global information base. A preliminary experiment using on-line technical reports, a representative subset of the Internet, shows the advantages of such an approach. A multiple layered database is a database formed by generalization and transformation of the information, layer-by-layer, starting from the original information base (treated as layer-0, the primitive layer). Information retrieval, data mining, and data analysis techniques can be used to extract and transform information from a lower layer database to a higher one. Layer-1 and higher layers of an MLDB can be modeled by an e...
Meta%2DRule%2DGuided Mining of Association Rules in Relational Databases.
A meta-rule-guided data mining approach is proposed and studied which apphes meta-rules as a guidance at finding multiple-level association rules in large relational databases. A meta-rule is a rule template in the form of &#034;P A ... A P, --* Q A...A Q,,&#034;, in which some of the predicates (and/or their variables) in the antecedent and/or consequent of the meta-rule could be instantJared. The rule template is used to describe what forms of rules are expected to be found from the database, and such a rule template is used as a guidance or constraint in the data mining process. Note that the predicate variables in a meta-rule can be instantJared against a database schema, whereas the variables or some high-level constants inside a predicate can be bound to multiple (but more specific) levels of concepts in the corresponding con- ceptual hierarchies. The concrete rules at different concept levels are discovered by a progressive deepening data mining technique similar to that developed in our study of mining multiple-level association rules. Two algorithms are developed along this hne and a performance study is conducted to compare their relative efficiencies. Our experimental and performance studies demonstrate that the method is powerful and efficient in data mining from large databases.

Maintenance of Discovered Knowledge A Strategy for Updating Association Rules %28Abstract%29.

Discovery of Spatial Association Rules in Geographic Information Databases.
Abstract. Spatial data mining, i.e., discovery of interesting, implicit knowledge in spatial databases, is an important task for understanding and use of spatial data- and knowledge-bases. In this paper, an e cient method for mining strong spatial association rules in geographic information databases is proposed and studied. A spatial association rule is a rule indicating certain association relationship among a set of spatial and possibly some nonspatial predicates. A strong rule indicates that the patterns in the rule have relatively frequent occurrences in the database and strong implication relationships. Several optimization techniques are explored, including a two-step spatial computation technique (approximate computation on large sets, and re ned computations on small promising patterns), shared processing in the derivation of large predicates at multiple concept levels, etc. Our analysis shows that interesting association rules can be discovered e ciently in large spatial databases. 1
Discovery of Multiple%2DLevel Association Rules from Large Databases.
Previous studies on mining association rules find rules at single concept level, however, mining association rules at multiple concept levels may lead to the discovery of more specific and concrete knowledge from data. In this study, a top-down progressive deepening method is developed for mining multiplelevel association rules from large transaction databases by extension of some existing association rule mining techniques. A group of variant algorithms are proposed based on the ways of sharing intermediate results, with the relative performance tested on different kinds of data. Relaxation of the rule conditions for finding &#034;level-crossing&#034; association rules is also discussed in the paper.
Chain%2DSplit Evaluation in Deductive Databases.
Many popularly studied recursions in deductive databases can be compiled into one or a set of highly regular chain generating paths, each of which consists of one or a set of connected predicates. Previous studies on chain-based query evaluation in deductive databases take a chain generating path as an inseparable unit in the evaluation. However, some recursions, especially many functional recursions whose compiled chain consists of infinitely evaluable function(s), should be evaluated by chain-split evaluation, which splits a chain generating path into two portions in the evaluation: an immediately evaluable portion and a delayed-evaluation portion. In this paper, the necessity of chain-split evaluation is examined from the points of view of both efficiency and finite evaluation, and three chain-split evaluation techniques: magic sets, buffered evaluation and partial evaluation, are developed. Our study shows that chain-split evaluation is a primitive recursive query evaluation techni...
Evaluation of Regular Nonlinear Recursions by Deductive Database Techniques.
Nonlinear recursion is one of the most challenging classes of logic programs for efficient evaluation in logic programming systems. We identify one popular class of nonlinear recursion,  regular nonlinear recursion, and investigate its efficient implementation by a deductive database approach. The approach performs a detailed query binding analysis based on query information, constraint information and the structure of a recursion, selects an appropriate predicate evaluation order and generates an efficient query evaluation plan. Interesting query evaluation techniques, such as chain-following, chain-split, and constraint pushing, are developed for the efficient evaluation of different kinds of queries. Furthermore, the technique can be extended to the evaluation of regular nonlinear recursions in HiLog and F-logic programs. The study not only presents a method for the evaluation of regular nonlinear recursions in a declarative way but also demonstrates the power of the deductive datab...
Information%2DAssociated Join Indices for Spatial Range Search.

Fact Updates in Logic Databases.

LogicBase A Deductive Database System Prototype.
A deductive database system prototype, LogicBase, has been developed, with an emphasis on efficient compilation and query evaluation of application-oriented recursions in deductive databases. The system identifies different classes of recursions and compiles recursions into chain or pseudo-chain forms when appropriate. Queries posed to the compiled recursions are analyzed systematically with efficient evaluation plans generated and executed, mainly based on a chain-based query evaluation method. The system has been tested using sophisticated recursions and queries with satisfactory performance. This paper introduces the general design principles and implementation techniques of the system and discusses its strength and limitations. 1 Introduction As an important extension to relational approach, research into deductive database systems represents a direction towards declarative query processing, high-level database programming, and integration of logic programming and relational databa...
Cooperative Query Answering Using Multiple Layered Databases.
How can a real-estate agent respond to inquiries quickly and intelligently? The `trick&#039; could be using a simple table to briefly outline the general information and a complete book to reference the details. Such a method can be generalized to the construction of a multiple layered database (MLDB), a useful database organization technique for cooperative query answering, database browsing, query optimization and querying cooperative information systems. In this paper, we study the construction of MLDBs using generalization and knowledge discovery techniques and the application of MLDBs to cooperative/intelligent query answering in database systems. 1 Introduction  Cooperative (or intelligent) query answering refers to a mechanism which answers queries cooperatively and intelligently by analyzing the intent of a query and providing some generalized, neighborhood, or associated answers [5, 11, 2]. Many interesting techniques [14, 6, 5, 10, 13, 15] have been developed for cooperative query...
How Does Knowledge Discovery Cooperate with Active Database Techniques in Controlling Dynamic Environment%3F
. A dynamic environment, such as a production process, a  communication network, highway traffic, etc., may contain a huge amount  of information, changing with time, which is a valuable resource for understanding  the general behavior of the environment, discovering the  regularities and anomalies currently happening in the environment, controlling  an evolution process, and intelligent modeling or managing the  environment. Unfortunately, the data generated in a dynamic environment  are often expressed in low level primitives and in huge volumes.  Because of the dynamic, continuous and rapid changes of the information  flow, it is difficult to catch the regularities and anomalies in a dynamic  environment and react promptly for real-time applications. In this study,  a knowledge discovery technique is integrated with data sampling and  active database techniques to discover interesting behaviors of a dynamic  environment and react intelligently to the environment changes. The discove...

Incremental Processing of Logic Database Relations.

Dynamic Generation and Refinement of Concept Hierarchies for Knowledge Discovery in Databases.
Concept hierarchies organize data and concepts in hierarchical forms or in certain partial order, which helps expressing knowledge and data relationships in databases in concise, high level terms, and thus, plays an important role in knowledge discovery processes. Concept hierarchies could be provided by knowledge engineers, domain experts or users, or embedded in some data relations. However, it is sometimes desirable to automatically generate some concept hierarchies or adjust some given hierarchies for particular learning tasks. In this paper, the issues of dynamic generation and refinement of concept hierarchies are studied. The study leads to some algorithms for automatic generation of concept hierarchies for numerical attributes based on data distributions and for dynamic refinement of a given or generated concept hierarchy based on a learning request, the relevant set of data and database statistics. These algorithms have been implemented in the DBLearn knowledge discovery syste...
DBLearn A System Prototype for Knowledge Discovery in Relational Databases.

Efficient and Effective Clustering Methods for Spatial Data Mining.
Spatial data mining is the discovery of interesting relationships and characteristics that may exist implicitly in spatial databases. In this paper, we explore whether clustering methods have a role to play in spatial data mining. To this end, we develop a new clustering method called CLARANS which is based on randomized search. We also de- velop two spatial data mining algorithms that use CLARANS. Our analysis and experiments show that with the assistance of CLARANS, these two algorithms are very effective and can lead to discoveries that are difficult to find with current spatial data mining algorithms.
Join Index Hierarchies for Supporting Efficient Navigations in Object%2DOriented Databases.

Delay%2DSensitive Multimedia on Disks.

Constraint%2DBased Query Evaluation in Deductive Databases.
Constraints play an important role in the efficient query evaluation in deductive databases. In this paper, constraint-based query evaluation in deductive databases is investigated, with the emphasis on linear recursions with function symbols. Constraints are classified into three classes: (i) rule constraints, (ii) integrity constraints, and (iii) query constraints. Techniques are developed for the maximal use of different kinds of constraints in rule compilation and query evaluation. Our study on the roles of different classes of constraints in set-oriented evaluation of linear recursions shows that (i) rule constraints should be integrated with their corresponding deduction rules in the compilation of recursions; (ii) integrity constraints, including finiteness constraints and monotonicity constraints, should be used in the analysis of finite evaluability and termination for specific queries; and (iii) query constraints, which are often useful in search space reduction and terminati...
A Study on the Structure of Linear Recursion.

Multichannel Delay Sensitive Data Retrieval.

Towards Efficient Induction Mechanisms in Database Systems.

Normalization of Linear Recursions in Deductive Databases.

Evaluation of Regular Nonlinear Recursive Programs.

Homomorphic Tree Embeddings and Their Applications to Recursive Program Optimization
This paper is concerned with the problems of stage preserving linearization and 1-boundedness for
Human%2DComputer Interfaces DBLEARN and System X.

An Attribute%2DOriented Rough Set Approach for Knowledge Discovery in Databases.
Knowledge Discovery in Databases (KDD) is an active research area with the promise for a high payoff in many business and scientific applications. The grand challenge of knowledge discovery in databases is to automatically process large quantities of raw data, identify the most significant and meaningful patterns, and present this knowledge in an appropriate form for achieving the user&#039;s goal. Knowledge discovery systems face challenging problems from the real-world databases which tend to be very large, redundant, noisy and dynamic. Each of these problems has been addressed to some extent within machine learning, but few, if any, systems address them all. Collectively handling these problems while producing useful knowledge efficiently and effectively is the main focus of the thesis. In this thesis, we develop an attribute-oriented rough set approach for knowledge discovery in databases. The method adopts the artificial intelligent &#034;learning from examples&#034; paradigm combined with rough...
Outline of the LogicBase Demonstration.

LogicBase A System Prototype for Deductive Query Evaluation.

Outline of the LogicBase Demonstration.

Data%2DDriven Discovery of Quantitative Rules in Relational Databases.
A quantitative rule is a rule associated with quantitative information which assesses the representativehess of the rule in the database. In this paper, an efficient induction method is developed for learuing quantitative rules in relational databases. With the assistance of knowledge about concept hierarchies, data relevance, and expected rule forms, attribute-oriented induction can be performed on the database, which integrates database operations with the learuing process and provides a simple, efficient way of learning quantitative rules from large databases. Our method learns both characteristic rules and classification rules. Quantitative information facilitates quantitative reasoning, incremental learning, and learuing in the presence of noise. Moreover, learuing qualitative rules can be treated as a special case of learuing quantitative rules. Our paper shows that attributeoriented induction provides an efficient and effective mechanism for learning various kinds of knowledge rules from relational databases.
Compilation and evaluation of linear mutual recursions.

Compilation%2DBased List Processing in Deductive Databases.

Efficient Deduction and Induction Key to the Success of Data%2DIntensive Knowledge%2DBase Systems.

Distance%2DAssociated Join Indices for Spatial Range Search.

Chain%2DSplit Evaluation in Deductive Databases.
Many popularly studied recursions in deductive databases can be compiled into one or a set of highly regular chain generating paths, each of which consists of one or a set of connected predicates. Previous studies on chain-based query evaluation in deductive databases take a chain generating path as an inseparable unit in the evaluation. However, some recursions, especially many functional recursions whose compiled chain consists of infinitely evaluable function(s), should be evaluated by chain-split evaluation, which splits a chain generating path into two portions in the evaluation: an immediately evaluable portion and a delayed-evaluation portion. In this paper, the necessity of chain-split evaluation is examined from the points of view of both efficiency and finite evaluation, and three chain-split evaluation techniques: magic sets, buffered evaluation and partial evaluation, are developed. Our study shows that chain-split evaluation is a primitive recursive query evaluation techni...
Chain%2DBased Evaluation %2D A Bridge Linking Recursive and Nonrecursive Query Evaluation.

Knowledge Discovery in Databases An Attribute%2DOriented Approach.
Knowledge discovery in databases, or data mining, is an important issue in the development of data- and knowledge-base systems. An attribute-oriented induction method has been developed for knowledge discovery in databases. The method integrates a machine learning paradigm, especially learning-from-examples techniques, with set-oriented database operations and extracts generalized data from actual data in databases. An attribute-oriented concept tree ascension technique is applied in generalization, which substantially reduces the computational complexity of database learning processes. Different kinds of knowledge rules, including characteristic rules, discrimination rules, quantitative rules, and data evolution regularities can be discovered efficiently using the attribute-oriented approach. In addition to learning in relational databases, the approach can be applied to knowledge discovery in nested relational and deductive databases. Learning can also be performed with databases containing noisy data and exceptional cases using database statistics. Furthermore, the rules discovered can be used to query database knowledge, answer cooperative queries and facilitate semantic query optimization. Based upon these principles, a prototyped database learning system, DBLEARN,  has been constructed for experimentation.
N%2DQueens Problem Revisited A Deductive Database Approach.

Compressed Counting Method.

Classification and Compilation of Linear Recursive Queries in Deductive Databases.

Automatic generation of compiled forms for linear recursions.

Binding Propagation Beyond the Reach of Rule%2FGoal Graphs.

Automatic generation of compiled forms for linear recursions.

Efficient Access Methods in Deductive and Object%2DOriented Databases.

On the Power of Query%2DIndependent Compilation.

Constraint%2DBased Reasoning in Deductive Databases.
Constraints play an important role in the efficient query evaluation in deductive databases. In this paper, constraint-based query evaluation in deductive databases is investigated, with the emphasis on linear recursions with function symbols. Constraints are classified into three classes: (i) rule constraints, (ii) integrity constraints, and (iii) query constraints. Techniques are developed for the maximal use of different kinds of constraints in rule compilation and query evaluation. Our study on the roles of different classes of constraints in set-oriented evaluation of linear recursions shows that (i) rule constraints should be integrated with their corresponding deduction rules in the compilation of recursions; (ii) integrity constraints, including finiteness constraints and monotonicity constraints, should be used in the analysis of finite evaluability and termination for specific queries; and (iii) query constraints, which are often useful in search space reduction and terminati...
Efficient Evaluation of Linear Recursions with Function Sysmbols in Deductive Databases.

Attribute%2DOriented Induction in Relational Databases.
Knowledge discovery in databases, or data mining, is an important issue in the development of data- and knowledge-base systems. An attribute-oriented induction method has been developed for knowledge discovery in databases. The method integrates a machine learning paradigm, especially learning-from-examples techniques, with set-oriented database operations and extracts generalized data from actual data in databases. An attribute-oriented concept tree ascension technique is applied in generalization, which substantially reduces the computational complexity of database learning processes. Different kinds of knowledge rules, including characteristic rules, discrimination rules, quantitative rules, and data evolution regularities can be discovered efficiently using the attribute-oriented approach. In addition to learning in relational databases, the approach can be applied to knowledge discovery in nested relational and deductive databases. Learning can also be performed with databases containing noisy data and exceptional cases using database statistics. Furthermore, the rules discovered can be used to query database knowledge, answer cooperative queries and facilitate semantic query optimization. Based upon these principles, a prototyped database learning system, DBLEARN,  has been constructed for experimentation.
Learning in relational databases an attribute%2Doriented approach.

Efficient Evaluation of Multiple Linear Recursions.

Evaluation of functional linear recursions a compilation approach.

An Attribute%2DOriented Approach for Learning Classification Rules from Relational Databases.

Path An Approach to Incorporate List Processing in A Relational Database.

From transitive closure recursions to single%2Dchain recursions.

Asynchronous Chain Recursions.
Synchronous chain recursions are a very frequent form of query in deductive database systems. Efficient query-processing is required, and algorithms suitable for parallel processing are needed. This paper generalises the arithmetic method of query answering (by integer arithmetic on path lengths in the query subgraph of the database diagraph) to N-chain recursions. Introduction Two assumptions which pervade the DDB literature are: i) no single evaluation can work efficiently on all forms of recursive query ii) the majority of DDB queries are single-linear recursions. (Also known as linear sirups and canonical strongly linear (SL) queries). Accordingly, efficient DDB systems use a number of different query processing methods, and performance can be significantly improved by efficiently handling linear recursions. There are usually two ways to improve DDB systems performance: i) develop efficient query processing algorithm and ii) make use of parallel processing. N-chain recursions a...
The Level%2DCycle Merging Method.

Processing Multiple Linear Recursions.

Derivation of Magic Sets by Compilation.

Compiling general linear recursions by variable connection graph analysis.

Asynchronous Chain Recursions.
Synchronous chain recursions are a very frequent form of query in deductive database systems. Efficient query-processing is required, and algorithms suitable for parallel processing are needed. This paper generalises the arithmetic method of query answering (by integer arithmetic on path lengths in the query subgraph of the database diagraph) to N-chain recursions. Introduction Two assumptions which pervade the DDB literature are: i) no single evaluation can work efficiently on all forms of recursive query ii) the majority of DDB queries are single-linear recursions. (Also known as linear sirups and canonical strongly linear (SL) queries). Accordingly, efficient DDB systems use a number of different query processing methods, and performance can be significantly improved by efficiently handling linear recursions. There are usually two ways to improve DDB systems performance: i) develop efficient query processing algorithm and ii) make use of parallel processing. N-chain recursions a...
Multi%2Dway counting method.

The Processing and Evaluation of Transitive Closure Queries.

Semantic Query Optimization in Recursive Databases.

What Kinds of Recursion Can Be Processed by Transitive Closure Strategies%3F

Selection of Processing Strategies for Different Recursive Queries.

One%2DDirectional Recursive Formulas.

Classification of Recursive Formulas in Deductive Databases.

Handling Redundancy in the Processing of Recursive Database Queries.

Some Performance Results on Recursive Query Processing in Relational Database Systems.

